type point=^rec;
rec=record
next:point;
endv:integer;
w:longint;
end;
var head,adj:array[1..20000]of point;
p,null:point;
n:integer;e:longint;start,over:integer;
open,closed:longint;
q:array[0..1000000]of integer;
flag:array[1..20000]of boolean;
dist:array[1..20000]of longint;
procedure init;
var i,stv,edv:integer;
wei:longint;
begin
fillchar(q,sizeof(q),0);
fillchar(flag,sizeof(flag),false);
fillchar(dist,sizeof(dist),127);
readln(n,e);
for i:=1 to n do
begin
new(p);
head[i]:=p;
adj[i]:=p;
end;
for i:=1 to e do
begin
readln(stv,edv,wei);
adj[stv]^.endv:=edv;
adj[stv]^.w:=wei;
new(p);
adj[stv]^.next:=p;
adj[stv]:=p;
/////symmetry/////
adj[edv]^.endv:=stv;
adj[edv]^.w:=wei;
new(p);
adj[edv]^.next:=p;
adj[edv]:=p
end;
for i:=1 to n do
adj[i]^.next:=null;
start:=1;over:=n;
end;
procedure spfa(s:longint);
var dady:integer;
begin
flag[s]:=true;q[1]:=s;dist[s]:=0;
open:=1;closed:=1;
while open<=closed do
begin
dady:=q[open];
p:=head[dady];
while (p<>nil) do
begin
if dist[p^.endv] > dist[dady]+p^.w
then begin
dist[p^.endv] := dist[dady]+p^.w;
if not flag[p^.endv]
then begin
inc(closed);
q[closed]:=p^.endv;
flag[p^.endv]:=true;
end;
end;
p:=p^.next;
end;
flag[dady]:=false;
inc(open);
end;
end;
begin
init;
null:=nil;
spfa(start);
writeln(dist[over]);
readln;readln;
end.