记录编号	49181	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	乔治文	是否通过	通过
代码语言	Pascal	运行时间	0.921 s
提交时间	2012-11-07 14:28:50	内存使用	0.32 MiB

var i,j,n,k,m,p,t,x,y,qq:longint;
    f:array[0..200,0..200] of longint;
begin
assign(input,'hardest.in');
reset(input);
assign(output,'hardest.out');
rewrite(output);

read(p);
for t:=1 to p do
 begin

  read(n,m);
  for i:=0 to n do
   for j:=0 to n do
   if i=j
    then f[i,j]:=0
    else f[i,j]:=-1;
  for i:=1 to m do
   begin
    read(x,y);
   read(qq);
   if (qq<f[x,y])or(f[x,y]=-1)
     then begin
           f[x,y]:=qq;
           f[y,x]:=f[x,y];
          end;
   end;

  for k:=1 to n do
   for i:=1 to n do
    for j:=1 to n do
     begin
      if ((f[i,j]>f[i,k]+f[k,j])or(f[i,j]=-1))and((f[i,k]<>-1)and(f[k,j]<>-1))
       then f[i,j]:=f[i,k]+f[k,j];
     end;
  writeln(f[1,n]);
 end;
close(input);
close(output);

end.