#include <bits/stdc++.h> using namespace std; const int maxn = 1e3+10; const int maxm = 6e4+10; struct Edge{ int v,next,c; }edge[maxm]; int head[maxn]; int tot; int s,t; int vis[maxn]; int dfn[maxn]; int low[maxn]; int bridge[maxm]; int Index; void init(){ memset(head,-1, sizeof(head)); memset(vis,0, sizeof(vis)); tot=0; } void add_edge(int u,int v,int c){ edge[tot].v = v; edge[tot].next = head[u]; edge[tot].c = c; head[u]=tot++; } bool dfs(int u,int fa,int del, vector<int>& path){ vis[u]=1; if(u==t) return true; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==fa||(i>>1)==del) continue; if(!vis[v]&&dfs(v,u,del,path)){ path.push_back(i>>1); return true; } } return false; } void tarjan(int u,int fa,int del){ dfn[u]=low[u]=++Index; int flag=0; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if((i>>1)==del) continue; if(v==fa&&!flag){ flag=1; continue; } if(!dfn[v]){ tarjan(v,u,del); low[u]=min(low[v],low[u]); if(low[v]>dfn[u]) bridge[i>>1]=1; } else low[u]=min(dfn[v],low[u]); } } int main(){ int n,m; scanf("%d%d", &n, &m); { scanf("%d%d", &s, &t); init(); for(int i=0;i<m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add_edge(a,b,c); add_edge(b,a,c); } vector<int> path; path.clear(); if(!dfs(s,-1,-1,path)){ printf("0\n0\n"); } else{ int ans=2e9+1; vector<int> ret; ret.clear(); for(int i=0;i<path.size();i++){ memset(dfn,0, sizeof(dfn)); memset(bridge,0, sizeof(bridge)); memset(vis,0, sizeof(vis)); Index=0; for(int j=1;j<=n;j++){ if(!dfn[j]) tarjan(j,-1,path[i]); } vector<int> tmp; if(!dfs(s,-1,path[i],tmp)){ if(ans>edge[path[i]*2].c){ ans=edge[path[i]*2].c; ret.clear(); ret.push_back(path[i]+1); } } else{ for(int j=0;j<tmp.size();j++){ if(bridge[tmp[j]]){ if(ans>edge[path[i]*2].c+edge[tmp[j]*2].c){ ans=edge[path[i]*2].c+edge[tmp[j]*2].c; ret.clear(); ret.push_back(path[i]+1); ret.push_back(tmp[j]+1); } } } } } if(ans>2e9) printf("-1\n"); else{ printf("%d\n%d\n", ans, ret.size()); for(int i=0;i<ret.size();i++){ printf("%d",ret[i]); if(i==ret.size()-1) puts(""); else printf(" "); } } } } return 0; }
|