#include<iostream>
#include<vector>
#include<map>
#include<limits.h>
#include<stdio.h>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int,int>Edge;//pair<cost,node>first,second;
struct Node{
 int cost;
 vector<Edge> edge;
 bool operator<(const Node&node) const{
   return(cost<node.cost);
 }
 bool operator>(const Node&node) const{
   return(cost>node.cost);
 }
 /*Node a,b;
   a.cost=5;
   b.cost=3;
   a.operator<(b); //false=0 //a<bと同じ
   b.cost=8;
   a.operator<(b); //true=1
 */
};
int main(){
 int n,e,from,to,cost;
 cin>>n>>e;
 vector<Node> node(n+1);
 for(int i=0;i<e;i++){
   cin>>from>>to>>cost;
   node[from].edge.push_back(Edge(cost,to));
   node[to].edge.push_back(Edge(cost,from));
   node[from].cost=INT_MAX;
   node[to].cost=INT_MAX;
 }
 /*priority_queue<Node> q;
 for(int i=1;i<=n;i++){
   q.push(node[i]);
 }
 while(!q.empty()){
   Node a;
   a=q.top();
   q.pop();
   cout<<a.cost<<" ";
 }
 cout<<endl;
 */

 /*
   typedef pair<int,int>Edge;
   typedef pair<int,Edge>Node;

   vector<Node> node;

   node[i].first; //コスト
   node[i].second[j].first; //j番目のエッジのコスト
   node[j].second[j].second; //j番目の接続先ノード
 */
 priority_queue<Node,vector<Node>,greater<Node> > q;
 int start=0;
 node[start].cost=0;
 q.push(node[start]);
 while(!q.empty()){
   Node done;
   done=q.top();//確定ノード
   q.pop();
   for(int i=0;i<done.edge.size();i++){
     int to=done.edge[i].second;
     int cost=done.edge[i].first+node[to].cost;

     if(node[to].cost>cost){
   node[to].cost=cost;
   q.push(node[to]);
     }
   }
 }
 cout<<node[n].cost<<endl;
 return 0;
}