;const int N=1024;const int inf=0x7fffffff;struct Edge{int u,v,w,use,del;};vector<Edge>edge;vector<int>G[N];int n,m,dist[N],inq[N],mp[N][N],path[N],d[N];void spfa(){int i,u,v;memset(inq,0,sizeof(inq));memset(mp,0,sizeof(mp));for(i=1;i<=n;i++){dist[i]=inf;path[i]=1;}dist[1]=0;queue<int>q;q.push(1);inq[1]=1;while(!q.empty()){u=q.front();q.pop();inq[u]=0;for(i=0;i<G[u].size();i++){int t=G[u][i];if(edge[t].del) continue;if(u==edge[t].u) v=edge[t].v;else v=edge[t].u;if(dist[v]>dist[u]+edge[t].w){dist[v]=dist[u]+edge[t].w;mp[u][v]=t;path[v]=u;if(inq[v]==0){q.push(v);inq[v]=1;}}}}}int main(){int _,i,j,u,v,w;Edge tp;scanf(“%d”,&_);while(_–){edge.clear();for(i=0; i<1024; i++) G[i].clear();scanf(“%d”,&n);scanf(“%d”,&m);for(i=0; i<m; i++){scanf(“%d%d%d”,&u,&v,&w);tp.u=u,tp.v=v,tp.w=w,tp.use=0,tp.del=0;edge.push_back(tp);G[u].push_back(i);G[v].push_back(i);}spfa();if(dist[n]==inf){printf(“-1\n”);continue;}int k1=n,k2=path[n];while(1){edge[mp[k2][k1]].use=1;if(k2==1) break;k1=k2;k2=path[k2];}int ans=-1;for(i=0; i<m; i++){if(edge[i].use){edge[i].del=1;spfa();if(dist[n]==inf){ans=-1;break;}ans=max(ans,dist[n]);edge[i].del=0;}}printf(“%d\n”,ans);}return 0;}
，勇于接受自己的不完美，认清自己不足的地方，
