#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f;
int mp[1010][1010],vis[1010],d[1010],n;
void dijkstra(){
	memset(d,INF,sizeof(d));
    d[1]=0;
	for(int step=1;step<=n;step++){
		int mi=INF;
		int id=-1;
		for(int i=1;i<=n;i++){
			if(d[i]<=mi&&!vis[i]){
				mi=d[i];
				id=i;
			}
		}
		vis[id]=1;
		for(int i=1;i<=n;i++){
			if(d[id]+mp[id][i]<d[i]){
				d[i]=d[id]+mp[id][i];
			}
		}
	}
	printf("%d\n",d[n]);
}
int main(){
	memset(mp,INF,sizeof(mp));
	int m;
	scanf("%d%d",&n,&m);
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		mp[a][b]=mp[b][a]=min(mp[a][b],c);
	}
	dijkstra();
	return 0;
}