记录编号	49108	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	limitation	是否通过	通过
代码语言	Pascal	运行时间	0.740 s
提交时间	2012-11-07 12:53:28	内存使用	0.51 MiB

program hardest;
 var t,i,j,k,x,y,n,loop,m,w:longint;
     a:array[1..300,1..300]of longint;
  begin
   assign(input,'hardest.in');
   reset(input);
   assign(output,'hardest.out');
   rewrite(output);
   read(t);
   for loop:=1 to t do
    begin
     read(n,m);
     for i:=1 to n do
      for j:=1 to n do
       a[i,j]:=100000;
     for i:=1 to n do
      a[i,i]:=0;
     for i:=1 to m do
      begin
       read(x,y,w);
       if a[x,y]>w then
        a[x,y]:=w;
       a[y,x]:=a[x,y];
      end;
     for k:=1 to n do
      for i:=1 to n do
       for j:=1 to n do
        if a[i,j]>a[i,k]+a[k,j] then a[i,j]:=a[i,k]+a[k,j];
     if a[1,n]<>100000then writeln(a[1,n]) else write(-1);
    end;
    close(input);
    close(output);
  end.