1 /*
 2 Author:    Leo.W
 3 Descriptipn:    給定圖上的n個(gè)點(diǎn)及m條點(diǎn)間連線，試求從S點(diǎn)到W點(diǎn)的最短距離，若不存在，則輸出-1;  
 4 How to Do:    經(jīng)典的最短路算法的應(yīng)用，dijkstra算法自編寫
 5   */
 6 #include <iostream>
 7 using namespace std;
 8 int n,m;//點(diǎn)的個(gè)數(shù)，點(diǎn)間連線的條數(shù)
 9 int path[205][1005];
10 bool node[205];
11 int Dijkstras(int s,int w){
12     int i,j;
13     node[s]=true;
14     for(i=0;i<n;i++){
15         int mins=INT_MAX,pos=s;
16         for(j=0;j<n;j++){//尋找為選入點(diǎn)的最小值
17             if(!node[j]&&mins>path[s][j]){
18                 mins=path[s][j]; pos=j;
19             }
20         }
21         if(mins==INT_MAX||j>n)    break;
22         node[pos]=true;
23         for(j=0;j<n;j++){
24             if(!node[j]&&path[pos][j]!=INT_MAX&&path[s][j]>path[s][pos]+path[pos][j]){
25                 path[s][j]=path[s][pos]+path[pos][j];
26                 path[j][s]=path[s][j];
27             }
28         }
29     }
30     return path[s][w];
31 }
32 int main(){
33     //freopen("in.txt","r",stdin);
34     while(scanf("%d%d",&n,&m)!=EOF){
35         int i,j;
36         for(i=0;i<n;i++){
37             node[i]=false;
38             for(j=0;j<n;j++){
39                 if(j==i)    path[i][j]=0;
40                 else    path[i][j]=INT_MAX;//表示兩點(diǎn)間無通路
41             }
42         }
43         for(i=0;i<m;i++){
44             int begin,end,len;
45             scanf("%d%d%d",&begin,&end,&len);
46             if(len<path[begin][end])//此處是全題關(guān)鍵，WA了很久。。。。【審題要細(xì)致啊】
47                 path[begin][end]=path[end][begin]=len;//雙向賦值
48         }
49         int s,w;
50         scanf("%d%d",&s,&w);
51         if(s>w){
52             s=s^w;w=s^w;s=s^w;
53         }
54         if(s==w)
55             printf("0\n");
56         else{
57             int ans=Dijkstras(s,w);
58             if(ans==INT_MAX)    printf("-1\n");
59             else    printf("%d\n",ans);
60         }
61     }
62     return 0;
63 }