program ex;
  type pt=^dy;
    dy=record
    link,data:Longint;
    next:pt;
    end;
    var a:array[1..200]of dy;
      v:array[1..200] of boolean;
      q:array[1..200000] of longint;
      d:array[1..200] of longint;
        t,n,x,y,z,head,tail,i,j,k,m:longint;
        p:pt;
  procedure lian(x,y,z:longint);
   begin
    new(p);
    p^.link:=y;
    p^.data:=z;
    p^.next:=a[x].next;
    a[x].next:=p;
   end;
  procedure spfa;
   begin
    while head<=tail do
     begin
      p:=a[q[head]].next;
       while p<>nil do
        begin
         if d[p^.link]>d[q[head]]+p^.data then
          begin
           d[p^.link]:=d[q[head]]+p^.data;
           if not(v[p^.link]) then
            begin
             inc(tail);
             q[tail]:=p^.link;
             v[p^.link]:=true;
            end;
          end;
         p:=p^.next;
        end;
      v[q[head]]:=false;
      inc(head);
     end;
   end;
        begin
        assign(input,'hardest.in');
        assign(output,'hardest.out');
        reset(input);
        rewrite(output);
         read(t);
         for i:=1 to t do
          begin
           read(n,m);
            for j:=1 to n do
             a[j].next:=nil;
            for j:=1 to m do
             begin
             read(x,y,z);
              lian(x,y,z);
              lian(y,x,z);
             end;
            fillchar(v,sizeof(v),false);
            fillchar(d,sizeof(d),$7f);
            fillchar(q,sizeof(q),0);
            d[1]:=0;
            q[1]:=1;
            v[1]:=true;
            head:=1; tail:=1;
          spfa;
         writeln(d[n]);
         end;
         close(input); close(output);
        end.