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