type alice=record

x,y,next,t:longint;

end;

var n,head,tail,m,i,j,x,y,best,k,tt,tot:longint;

first,q,dis:array[1..1000000]of longint;

bian:array[1..1000000]of alice;

v:array[1..1000000]of boolean;

procedure connect(a,b,c:Longint);

begin

inc(tot);

with bian[tot] do

begin

x:=a;

y:=b;

t:=c;

next:=first[x];

first[x]:=tot;

end;

end;

begin

readln(n,m);

for i:=1 to m do

begin

readln(x,y,tt);

connect(x,y,tt);

connect(y,x,tt);

end;

fillchar(v,sizeof(v),false);

for i:=1 to n do dis[i]:=maxlongint shr 1;

head:=0;

tail:=1;

q[1]:=1;

dis[1]:=0;

v[1]:=true;

repeat

inc(head);

x:=q[head];

k:=first[x];

while k<>0 do

begin

y:=bian[k].y;

if dis[y]>dis[x]+bian[k].t then

begin

dis[y]:=dis[x]+bian[k].t;

if not v[y] then

begin

inc(tail);

q[tail]:=y;

v[y]:=true;

end;

end;

k:=bian[k].next;

end;

v[x]:=false;

until head=tail;

writeln(dis[n]);

end.

二维数组不够用，用数组模拟指针，再用spfa