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

var t,n,i,j,k,l,o,m:longint; d:array[1..200]of longint; v:array[1..200]of boolean;
    c:array[1..200,1..200]of longint;
begin
assign(input,'hardest.in'); assign(output,'hardest.out'); reset(input); rewrite(output);
 readln(t); for o:=1 to t do begin
  readln(n,m); fillchar(d,sizeof(d),$5f); fillchar(v,sizeof(v),false); fillchar(c,sizeof(c),0); d[1]:=0;
  for i:=1 to m do begin readln(j,k,l); if(c[j,k]=0)or(c[j,k]>l)then begin c[j,k]:=l; c[k,j]:=l; end; end; l:=0;
  repeat
   j:=maxlongint;
   for i:=1 to n do
    if not(v[i])and(d[i]<j)then
     begin j:=d[i]; k:=i; end;
   v[k]:=true; inc(l);
   for i:=1 to n do
    if(c[k,i]<>0)and(d[k]+c[k,i]<d[i])then
     d[i]:=d[k]+c[k,i];
  until l=n;
  if d[n]>2000000 then write(-1) else writeln(d[n]);
 end;
close(input); close(output);
end.