#include<iostream>

 #include<cstring>

 using namespace std;

 int n,m;

 int dist[];

 bool ok[];

 int ma[][];

 int main(){

     cin>>n>>m;

     memset(ma,0x3f,sizeof(ma));//先设置为无穷大

     for(int i=;i<=m;i++){    //读入

         int a,b,c;

         cin>>a>>b>>c;

         ma[a][b]=c;

         ma[b][a]=c;

     }

     memset(dist,0x3f,sizeof(dist));//将到每一个点的最短路设置为无穷大

     dist[]=;

     for(int i=;i<=n;i++){            //主要步骤

         int mmm,minn=0x3f3f3f;

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

             if(!ok[j]&&dist[j]<minn){

                 minn=dist[j];

                 mmm=j;

             }

         }

         ok[mmm]=;

         for(int k=;k<=n;k++){

             dist[k]=min(dist[k],dist[mmm]+ma[mmm][k]);

         }

     }

     cout<<dist[n];

     return ;

 }