记录编号	49206	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	zzc	是否通过	通过
代码语言	Pascal	运行时间	0.090 s
提交时间	2012-11-07 14:59:07	内存使用	0.33 MiB

var i,j,k,h,n,m,t,a,b,w,ans,min:longint;
        v:array[0..210,0..210] of longint;
        d:array[0..210] of longint;
        f:array[0..210] of boolean;

begin
assign(input,'hardest.in');
reset(input);
assign(output,'hardest.out');
rewrite(output);
readln(t);
for k:=1 to t do
        begin
        readln(n,m);
        for i:=1 to n do
        for j:=1 to n do v[i,j]:=999999999;
        for i:=1 to n do v[i,i]:=0;
        for i:=1 to n do d[i]:=999999999;
        fillchar(f,sizeof(f),false);
        f[1]:=true;
        d[1]:=0;
        for i:=1 to m do
                begin
                readln(a,b,w);
                if (v[a,b]>w) then
                v[a,b]:=w;
                v[b,a]:=v[a,b];
                end;
               for i:=1 to n do d[i]:=v[1,i];
        for j:=1 to n-1 do
                begin
                min:=999999999;  h:=-1;
                for i:=1 to n do
                if (not f[i]) and (d[i]<min) then
                begin h:=i;min:=d[i];end;
                if h=-1 then break;
                f[h]:=true;
                for i:=1 to n do
                if (not f[i]) and (d[h]+v[h,i]<d[i]) then
                        d[i]:=d[h]+v[h,i];
                end;

        if d[n]<999999999 then writeln(d[n]) else writeln('-1');
        end;
close(input);
close(output);
end.