1 #include<iostream>
2 #include<set>
3 #include<cstdio>
4 using namespace std;
5 #define N 10000
6 #define M 100000
7 int dist[N],start[N];
8 bool vis[N];
9 struct node{
10 int en,w,next;
11 } list[M];
12 struct cmp{
13 bool operator()(const int &a,const int &b)const{
14 return (dist[a]<dist[b])||((dist[a]==dist[b])&&(a<b));
15 }
16 };
17 void adde(int x,int y,int we,int tot){
18 list[tot].en=y;list[tot].w=we;list[tot].next=start[x];start[x]=tot;
19 }
20 int dijkstra(int st,int en){
21 set<int,cmp>s;
22 memset(vis,true,sizeof(vis));
23 memset(dist,0x7f,sizeof(dist));
24 dist[st]=0;
25 s.clear();
26 s.insert(st);
27 while(!s.empty()){
28 int x=*s.begin();
29 s.erase(x);
30 vis[x]=false;
31 int t=start[x];
32 while(t){
33 int y=list[t].en;
34 if((vis[y])&&(dist[x]+list[t].w<dist[y])){
35 s.erase(y);
36 dist[y]=dist[x]+list[t].w;
37 s.insert(y);
38 }
39 t=list[t].next;
40 }
41 }
42 printf("%d\n",dist[en]);
43 }
44 int main(){
45 int en,st,n,m,tot=0;
46 cin>>n>>m;
47 memset(start,0,sizeof(start));
48 for(int i=1;i<=m;i++){
49 int x,y,we;
50 scanf("%d%d%d",&x,&y,&we);
51 adde(x,y,we,++tot);
52 adde(y,x,we,++tot);
53 }
54 cin>>st>>en;
55 dijkstra(st,en);
56 return 0;
57 }
58 /*
59
60 4 5
61 1 2 3
62 2 4 3
63 1 4 7
64 1 3 2
65 3 4 6
66 1 4
67
68 */
69