// 单源：Bellman-Ford/SPFA
// O(n*m)可以处理负权边，还能检测负环 
// solution:用队列维护拓展点 
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 1e3;
typedef struct edge{
    int v,w;  // 连接点编号，边权重 
    edge(int v0,int w0):v(v0),w(w0){}
    bool operator >(const edge &b)const{
        return w>b.w;
    }
}edge;
int n;  // 点数
int dist[MAXN+10];
int in[MAXN+10];  // in the queue?
vector<edge> G[MAXN+10];  // 用edge的vector保存整个图，G[i]表示以i点为起点的边的数组 
void dijkstra(int p_s){  // p_s 为起点下标 
    for(int i=1;i<=n;i++){  // in初始化 
        dist[i] = 0x3f3f3f3f;
        in[i] = 0; 
    }  
    dist[p_s] = 0;
    for(int iii=0;iii<n;iii++){
        // findmin
        int minn = 0x3f3f3f3f;
        int minpos = 0;
        for(int i=1;i<=n;i++){
            if(!in[i]&&dist[i]<minn){
                minn = dist[i];
                minpos = i;
            }
        }
        if(minpos==0){
            //cout<<"非连通图"<<endl;
            break;
        }
        // 最近点入集合并更新 
        in[minpos] = 1;
        for(int i=0;i<G[minpos].size();i++){
            int v = G[minpos][i].v;
            if(dist[v]>minn+G[minpos][i].w){
                dist[v] = minn+G[minpos][i].w;
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(false);
    int T,N;  // 点数，边数。
    cin>>N>>T;
    n = N;
    for(int i=0;i<T;i++){
        int v1,v2,w;
        cin>>v1>>v2>>w;
        G[v1].push_back(edge(v2,w));
        G[v2].push_back(edge(v1,w));    
    }
    dijkstra(1); 
    cout<<dist[N]<<endl;
    
    return 0;
}