dist:array[-10..30010] of longint;
q:array[-10..150010] of longint;
flag:array[-10..30010] of boolean;
n,m,a,b,w,i:longint;
procedure init;
begin
fillchar(dist,sizeof(dist),127);
fillchar(path,sizeof(path),0);
fillchar(flag,sizeof(flag),false);
fillchar(q,sizeof(q),0);
readln(n,m);
for i:=1 to m do
begin
readln(a,b,w);
path[a,b]:=w;
path[b,a]:=w;
end;
dist[1]:=0;
end;
function relax(u,v:longint):boolean;
begin
if (path[u,v]<>0) and (dist[u]+path[u,v]<dist[v]) then
begin
dist[v]:=dist[u]+path[u,v];
exit(true);
end
else exit(false);
end;
procedure spfa(s:longint);
var h,t,v:longint;
begin
h:=0;t:=0;
inc(t);q[t]:=s;flag[s]:=true;
while h<>t do
begin
h:=(h mod n)+1;
v:=q[h];
flag[v]:=false;
for i:=1 to n do
if relax(v,i) then
if not flag[i] then
begin
t:=(t mod n)+1;
q[t]:=i;
flag[i]:=true;
end;
end;
end;
begin
init;
spfa(1);
writeln(dist[n]);
end.