1 /* *********************************************** 2 Author        :SunYuefeng 3 Created Time  :2016/10/22 14:18:06 4 File Name     :A.cpp 5 ************************************************ */ 6  7 #include<cstdio> 8 #include<iostream> 9 #include<algorithm>10 #include<cmath>11 #include<cstring>12 #include<string>13 #include<bitset>14 #include<map>15 #include<set>16 #include<stack>17 #include<vector>18 #include<queue>19 #include<list>20 #define M(a,b) memset(a,b,sizeof(a))21 using namespace std;22 typedef long long ll;23 const int inf=0x3f3f3f3f;24 const int maxn=1e3+10;25 const int mod=1e7+7;26 int dx[8]= {0,0,1,-1,1,-1,1,-1};27 int dy[8]= {1,-1,0,0,-1,1,1,-1};28 29 int n,m;30 int way[maxn][maxn];31 int dis[maxn];32 bool vis[maxn];33 34 void dijkstra(int x){35     for(int i=1;i<=m;i++){36         dis[i]=inf;37         vis[i]=false;38     }39     dis[x]=0;40     for(int i=1;i<=m;i++){41         int k=-1;42         int min=inf;43         for(int j=1;j<=m;j++){44             if(!vis[j]&&dis[j]<min){45                 min=dis[j];46                 k=j;47             }48         }49         if(k==-1) break;50         vis[k]=true;51         for(int j=1;j<=m;j++){52             if(!vis[j]&&dis[j]>dis[k]+way[j][k]){53                 dis[j]=dis[k]+way[j][k];54             }55         }56     }57 }58 59 int main()60 {61     //freopen("in.txt","r",stdin);62     //freopen("out.txt","w",stdout);63     while(~scanf("%d%d",&n,&m)){64         int a,b,v;65         M(way,inf);66         for(int i=0;i<n;i++){67             scanf("%d%d%d",&a,&b,&v);68             if(way[a][b]>v){69                 way[a][b]=v;70                 way[b][a]=v;71             }72         }73         dijkstra(1);74         int min=inf;75         printf("%d\n",dis[m]);76     }77     return 0;78 }