#include<stdio.h>
#include<string.h>
#define min(a,b) (((a)<(b))?(a):(b))
#define inf 0x3f3f3f3f
int n,m;
struct edge {
int v,w,next;
}e[5005];
int p[1005],eid,d[1005],vis[1005];
void insert(int u,int v,int w) {
struct edge t={v,w,p[u]};
e[eid]=t;
p[u]=eid++;
}
void insert2(int u,int v,int w) {
insert(u,v,w);
insert(v,u,w);
}
int main() {
scanf("%d%d",&n,&m);
memset(p,-1,sizeof(p));
memset(d,inf,sizeof(d));
for(int i=0;i<m;i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
insert2(u,v,w);
}
d[1]=0;
for(int i=1;i<=n;i++) {
int mind=inf;
int u=0;
for(int j=1;j<=n;j++) {
if(!vis[j]&&d[j]<mind) {
mind=d[j];
u=j;
}
}
if(mind==inf) break;
vis[u]=1;
for(int j=p[u];~j;j=e[j].next) {
int v=e[j].v;
d[v]=min(d[v],d[u]+e[j].w);
}
}
printf("%d",d[n]);
return 0;
}