//Floyd
#include<bits/stdc++.h>
using namespace std;
int g[1010][1010]={};
int f[1010][1010]={};
int main(){
    int n,m;
    cin>>n>>m;//n个点,m边
    memset(g,126,sizeof(g));
    for(int i=1;i<=m;i++){
        int u,v,x;
        cin>>u>>v>>x;
        g[u][v]=g[v][u]=x;
    }
    memset(f,126,sizeof(f));
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                f[i][j]=g[i][j];
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
    cout<<f[1][n];
    return 0;
}