#include #include #include using namespace std; #include #include #include template vectordijkstra(int s,const vector > >&G,T INF=numeric_limits::max()) { int n=G.size(); vectord(n,INF); vectorparent(n,-1); priority_queue,vector >,greater > >P; d[s]=0; P.push(make_pair(d[s],s)); while(!P.empty()) { pairp=P.top();P.pop(); int v=p.second; if(d[v]&e:G[v]) { int u=e.first; T cost=d[v]+e.second; if(d[u]>cost) { d[u]=cost; parent[u]=v; P.push(make_pair(d[u],u)); } } } return d; } int n,m,L; long t[2000]; main() { cin>>n>>m>>L; int cnt=0; for(int i=0;i>t[i],cnt+=!!t[i]; if(cnt==1)cout<<0< > >G(n); for(int i=0;i>a>>b>>c; a--;b--; G[a].push_back(make_pair(b,c)); G[b].push_back(make_pair(a,c)); } vectoroff=dijkstra(L-1,G); long ans=9e18; for(int i=0;ia=dijkstra(i,G); for(int j=0;j