记录编号	49132	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	Pascal	运行时间	2.250 s
提交时间	2012-11-07 13:08:00	内存使用	0.24 MiB

var
t,n,m,q,i,j,a,b,k:integer;
f:array[0..201,0..201]of integer;
begin
assign(input,'hardest.in');reset(input);
assign(output,'hardest.out');rewrite(output);
read(t);
for q:=1 to t do
 begin
  read(n,m);
  //+++++++++++++++++++++++++++++
  for i:=1 to n do
   for j:=1 to n do
    if i=j then f[i,j]:=0
    else f[i,j]:=-1;
  //+++++++++++++++++++++++++++++
  for i:=1 to m do
   begin
    read(a,b,k);
    if (f[a,b]>k)or(f[a,b]=-1) then
     begin  f[a,b]:=k;f[b,a]:=k;end;
   end;
  //+++++++++++++++++++++++++++++
  for k:=1 to n do
   for i:=1 to n do
    if (i<>k)and(f[i,k]>-1) then
     for j:=1 to n do
      if ((f[i,j]=-1)and(f[j,k]>-1))or((i<>j)and(j<>k)and(f[i,j]>-1)and(f[j,k]>-1)and(f[i,k]+f[j,k]<f[i,j]))then
       begin f[i,j]:=f[i,k]+f[j,k];f[j,i]:=f[i,j];end;
  //+++++++++++++++++++++++++++++
   writeln(f[1,n]);
 end;
close(input);close(output);
end.