#include<bits/stdc++.h>
using namespace std;
int dis[105][105];
int x,y,z;
int n,m;
int main(){
cin>>n>>M;
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++){
dis[i][i]=0;
}
while(m--){
cin>>x>>y>>z;
dis[x][y]=dis[y][x]=min(dis[x][y],z);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
cout<<dis[1][n];
}
