1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 using namespace std;
6 const int MAXN=30001;
7 const int maxn=0x7fffffff;
8 struct node
9 {
10 int u;
11 int v;
12 int w;
13 int next;
14 }edge[MAXN];
15 int num=1;
16 int head[MAXN];
17 int n,m,begin,end;
18 int dis[MAXN];
19 int vis[MAXN];
20 void spfa()
21 {
22 for(int i=1;i<=n;i++)dis[i]=maxn;
23 queue<int>q;
24 vis[begin]=1;
25 q.push(begin);
26 dis[begin]=0;
27 while(q.size()!=0)
28 {
29 int p=q.front();
30 q.pop();
31 vis[p]=0;
32 for(int i=head[p];i!=-1;i=edge[i].next)
33 {
34 if(dis[edge[i].v]>dis[p]+edge[i].w&&dis[p]!=maxn)
35 {
36 dis[edge[i].v]=dis[p]+edge[i].w;
37 if(vis[edge[i].v]==0)
38 {
39 q.push(edge[i].v);
40 vis[edge[i].v]=1;
41 }
42 }
43 }
44 }
45 printf("%d",dis[end]);
46 }
47 int main()
48 {
49 scanf("%d%d%d%d",&n,&m,&begin,&end);
50 for(int i=1;i<=n;i++)head[i]=-1;
51 for(int i=1;i<=m;i++)
52 {
53 scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);
54 edge[num].next=head[edge[num].u];
55 head[edge[num].u]=num++;
56 edge[num].w=edge[num-1].w;
57 edge[num].u=edge[num-1].v;
58 edge[num].v=edge[num-1].u;
59 edge[num].next=head[edge[num].u];
60 head[edge[num].u]=num++;
61 }
62 spfa();
63 return 0;
64 }