#include <stdio.h>

 #include <string.h>

 #define p 65535//必须加括号；

 int m,n;

 int a[][], v[], d[];//v是标记数组，d数组是保存最小权值的数组，相当于lowcost数组

 void Dijkstra()//n在这里是节点数

 {

     //d数组说明：d数组中的每一个元素都保存住源节点到数组元素下标x的最短路的权值累加

     int i;

     memset(v ,  , sizeof(v));

     for(i = ; i <= n; i++)

         d[i] = a[][i];//第一个节点相接的所有边的权值都保存起来；

     v[] = ;//标记第一个，已被访问过；

     d[] = ;//第一个到自己的距离为0；

     for(i = ; i <= n-; i++)

     {

         int x, y, t = p;//让t为最大值

         for(y = ; y <= n; y++)

         {

             if(!v[y] && d[y] <= t)

             {

                 x=y;

                 t=d[x];//t保存住最小权值

             }

         }

         v[x] = ;//x已经访问完

         for(y = ; y <= n; y++)//更新法则和prim算法不相同，其余均相同

         {

             if(v[y]==)//这句有没有不影响结果，为什么？

             {

                 if(d[y] > t + a[x][y])

                 {

                     d[y] = t + a[x][y];

                 }

             }

         }

     }

 }

 int main()

 {

     int  i, j;

     int t1, t2, t3;

     while(~scanf("%d %d",&n, &m))

     {

         for(i = ; i <= n; i++)

             for(j = ; j <= n; j++)

                 a[i][j] = p;

         for(i = ; i <= m; i++)

         {

             scanf("%d %d %d",&t1, &t2, &t3);

             if(a[t1][t2] > t3)//确保重复出现权值的问题，保证最小权值；

             {

                 a[t1][t2] = t3;

                 a[t2][t1] = t3;

             }

         }

         Dijkstra();

         printf("%d\n",d[n]);

     }

     return ;

 }

 #include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 int map[][];

 int m,n;

 int prim()

 {

     int lowcost[];

     int f[]={};

     int  g[];

     int i,j,min,k,sum=;

     lowcost[]=;

     f[]=;

     g[]=;

     for(i=;i<=m;i++)

       {

           lowcost[i]=map[][i];

           g[i]=;//本语句不可以省略

       }

     for(i=;i<=m;i++)

     {

         min=;

         for(j=;j<=m;j++)

             if(lowcost[j]<=min&&f[j]==)//寻找与已经生成的最小生成树邻接的边的最小权值

             {

                 min=lowcost[j];//min是最小权值

                 k=j;//k是最小权值边的终端所对应的数组元素的下标

             }

         //printf("%d->%d:%d\n",g[k],k,min);//本语句只是为表现出最小生成树的结构，g数组也是为此而定义，可省略该数组

         sum=sum+min;

         f[k]=;//表明f[k]元素已经用完，下次再碰到时直接跳过

         for(j=;j<=m;j++)//最重要的一步，不解释

         {

             if((map[k][j]+min)<lowcost[j]&&f[j]==)//修改处1

             {

             lowcost[j]=map[k][j]+min;

             g[j]=k;

             }

         }

     }

     return lowcost[m];//修改处2

 }

 int main()

 {

     while(scanf("%d%d",&m,&n)!=EOF)

     {

         int sum=;

          int i,j;

          for(i=;i<=;i++)

          for(j=;j<=;j++)

          map[i][j]=;//将map数组中的元素全部置为最大，表示各个节点之间无联系

          for(i=;i<=n;i++)

          {

              int u,v,w;

              scanf("%d%d%d",&u,&v,&w);

              if(map[u][v]>w)//防止出现输入2 3 3，2 3 4这样的情况，所以要比较求出最小权值

              {

                  map[u][v]=w;

                  map[v][u]=w;

              }

          }

           sum=prim();

          printf("%d\n",sum);

     }

 }