type link=^node；
node=record
a,d:longint；
next:link
end；
var a,d:array[1..30000] of longint；
v:array[1..30000] of boolean；
l:array[1..30000] of link；
s:array[1..300000] of longint；
i,j,n,m,p,c,x,y,ans,dis,q,h:longint；
t:link；
begin
readln(n,m)；
for i:=1 to n do l[i]:=nil；
for i:=1 to m do
begin
readln(x,y,dis)；
new(t)；t^.a:=y；t^.d:=dis；t^.next:=l[x]；l[x]:=t；
new(t)；t^.a:=x；t^.d:=dis；t^.next:=l[y]；l[y]:=t
end；
ans:=maxlongint；
for i:=1 to n do d[i]:=1000000000；
d[1]:=0；
v[1]:=true；
s[1]:=1；q:=0；h:=1；
while q<h do
begin
inc(q)；
t:=l[s[q]]；v[s[q]]:=false；
while t<>nil do
begin
if d[s[q]]+t^.d<d[t^.a]
then
begin
d[t^.a]:=d[s[q]]+t^.d；
if not v[t^.a] then begin v[t^.a]:=true；inc(h)；s[h]:=t^.a end
end；
t:=t^.next
end
end；
writeln(d[n])
end.
3000ms+++