1 #include<cstdio>
 2 #include<queue>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 
 7 struct edge
 8 {
 9     int from,to,dist;
10     edge(int u,int v,int w):from(u),to(v),dist(w){};
11 };
12 
13 struct heapnode
14 {
15     int u,d;
16     bool operator < (const heapnode &temp)const
17     {
18         return d>temp.d;
19     }
20 };
21 
22 const int inf=0x3f3f3f3f;
23 int m,n;
24 vector<edge>edges;
25 vector<int>G[205]; 
26 int vis[205],d[205];
27 
28 void init()
29 {
30     for(int i=0;i<m;i++)
31     G[i].clear();
32     edges.clear();
33     memset(vis,0,sizeof(vis));
34 }
35 
36 void addedge(int u,int v,int w)
37 {
38     edges.push_back(edge(u,v,w));
39     edges.push_back(edge(v,u,w));
40     int m=edges.size();
41     G[u].push_back(m-2); 
42     G[v].push_back(m-1);
43 }
44 
45 int dijkstra(int S,int T)
46 {
47     priority_queue<heapnode>q;
48     q.push((heapnode){S,0});
49     for(int i=0;i<m;i++)d[i]=inf;
50     d[S]=0;
51     while(!q.empty())
52     {
53         int u=q.top().u;
54         q.pop();
55         if(vis[u])
56         continue;
57         vis[u]=true;
58         for(int i=0;i<G[u].size();i++)
59         {
60             edge& e=edges[G[u][i]];
61             if(d[e.to]>d[u]+e.dist)
62             {
63                 d[e.to]=d[u]+e.dist;
64                 q.push((heapnode){e.to,d[e.to]});
65             }
66         }
67     }
68     return d[T];
69 }
70 
71 int main()
72 {
73     //freopen("in.txt","r",stdin);
74     int a,b,c,S,T;
75     while(scanf("%d%d",&m,&n)!=EOF)
76     {
77         init();
78         for(int i=0;i<n;i++)
79         {
80             scanf("%d%d%d",&a,&b,&c);
81             addedge(a,b,c);
82         }
83         scanf("%d%d",&S,&T);
84         int ans=dijkstra(S,T);
85         if(ans==inf)
86         printf("-1\n");
87         else
88         printf("%d\n",ans); 
89     }
90     return 0;
91 }