type point=^node;
     node=record
      ve:longint;
      next:point;
      data:longint;
     end;
var a:array[1..200] of node;
    f:array[1..1000000] of longint;
    v:array[1..200] of boolean;
    dis:array[1..200]of longint;
    i,n,m,t:longint;

procedure init;
  var x,y,z,i:longint;
      p:point;
  begin
   readln(n,m);
   for i:=1 to n do
   begin new(p); a[i].ve:=0; a[i].next:=nil; a[i].data:=0; end;
   for i:=1 to m do
   begin readln(x,y,z);
         new(p); a[x].ve:=x; p^.ve:=y; p^.next:=a[x].next; a[x].next:=p; p^.data:=z;
         new(p); a[y].ve:=y; p^.ve:=x; p^.next:=a[y].next; a[y].next:=p; p^.data:=z;
   end;
   end;

procedure spfa;
  var head,tail,now:longint;
      p:point;
  begin
  fillchar(v,sizeof(v),false);
  fillchar(dis,sizeof(dis),$7f);
  fillchar(f,sizeof(f),0);
  head:=0; tail:=1; f[1]:=a[1].ve;
  v[f[1]]:=true; dis[1]:=0;
  while head<>tail do
  begin
  inc(head); head:=head mod 1000000; now:=f[head];
  p:=a[now].next;
  while p<>nil do
  begin
  if dis[p^.ve]>dis[now]+p^.data then begin
     dis[p^.ve]:=dis[now]+p^.data;
     if not v[p^.ve] then begin inc(tail); tail:=tail mod 1000000;
                                  f[tail]:=p^.ve; v[f[tail]]:=true; end;
     end;
     p:=p^.next;
     end;
     v[f[head]]:=false;
     end;
     end;

begin
  assign(input,'hardest.in'); reset(input);
  assign(output,'hardest.out'); rewrite(output);
  readln(t);
  for i:=1 to t do
  begin
  init;
  spfa;
  writeln(dis[n]);
  end;
  close(output);
end.