#include using namespace std; #define rep(i,n) for(ll i=0;i>N>>M>>L; vector T(N); ll cnt=0; for(int i=0;i>T[i]; if(T[i]>0)cnt++; } if(cnt==1){ cout<<0<>> G(N); for(int i=0;i>a>>b>>c; a--;b--; G[a].push_back({b,c}); G[b].push_back({a,c}); } ll an=1e18; vector> dist(N); for(int i=0;i seen(N,false); priority_queue,vector>,greater>> Q; vector D(N,1e18); Q.push({0,i}); D[i]=0; while(!Q.empty()){ auto [c,p]=Q.top(); Q.pop(); if(seen[p])continue; seen[p]=1; for(auto [v,w]:G[p]){ if(seen[v])continue; if(D[v]<=c+w)continue; D[v]=c+w; Q.push({D[v],v}); } } dist[i]=D; } for(int i=0;i0)an=min(an,res-dist[i][j]*2+dist[i][j]+dist[L-1][j]); } } cout<