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

uses math;

var f:array[0..200]of longint;
    v:array[1..200]of boolean;
    a:array[1..200,1..200]of longint;
    b:array[1..200,0..10000]of longint;
    p:array[1..20000]of longint;
    i,k,x,now,y,z,n,m,t,head,tail:longint;

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);
   fillchar(b,sizeof(b),0);
   fillchar(a,sizeof(a),0);
   for i:=1 to m do
    begin
     readln(x,y,z);
     inc(b[x,0]);b[x,b[x,0]]:=y;
     if a[x,y]=0 then a[x,y]:=z else a[x,y]:=min(a[x,y],z);
     inc(b[y,0]);b[y,b[y,0]]:=x;
     if a[y,x]=0 then a[y,x]:=z else a[y,x]:=min(a[y,x],z);
    end;
   fillchar(v,sizeof(v),false);
   fillchar(f,sizeof(f),$7f);
   p[1]:=1;f[1]:=0;head:=0;tail:=1;
   while head<>tail do
    begin
     inc(head);
     now:=p[head];v[now]:=false;
     for i:=1 to b[now,0]do
      begin
       x:=b[now,i];
       if f[x]>f[now]+a[x,now] then
        begin
         f[x]:=f[now]+a[x,now];
         if not(v[x])then
          begin inc(tail);p[tail]:=x;v[x]:=true;end;
        end;
      end;
    end;
   if f[n]<>f[0]then writeln(f[n])else writeln('-1');
  end;
 close(output);
end.