program C1254;
 const Be=20000;
       Bf=200;
 var e,next:array[1..Be] of longint;
     head,dist:array[1..Bf] of longint;
     v:array[1..Bf] of boolean;
     q:array[1..Bf*5] of longint;
     S:array[1..Bf,1..Bf] of longint;
     n,a,b,l,m,i,T,j:longint;

 function Spfa(v0,vN:longint):longint;
  var i,t,h:longint;
  begin
   fillchar(v,sizeof(v),false);
   for i:=1 to n do dist[i]:=maxlongint;
   h:=0;

   t:=1;
   q[t]:=v0;
   v[v0]:=true;
   dist[v0]:=0;

   while h<>t do begin
    inc(h);
    i:=head[q[h]];
    v[q[h]]:=false;
    while i<>0 do begin
     if (S[q[h],e[i]]<>0) and (dist[e[i]]>dist[q[h]]+S[q[h],e[i]]) then begin
      dist[e[i]]:=dist[q[h]]+S[q[h],e[i]];
      if not v[e[i]] then begin
       v[e[i]]:=true;
       inc(t);
       q[t]:=e[i];
      end;
     end;
     i:=next[i];
    end;
   end;

   Spfa:=dist[vN];
  end;
 begin
  assign(input,'hardest.in');
  reset(input);
  assign(output,'hardest.out');
  rewrite(output);

  readln(T);

  for j:=1 to T do begin
   readln(n,m);

   for i:=1 to m do begin
    readln(a,b,l);

    e[i<<1-1]:=b;
    next[i<<1-1]:=head[a];
    head[a]:=i<<1-1;

    e[i<<1]:=a;
    next[i<<1]:=head[b];
    head[b]:=i<<1;

    S[a,b]:=l;
    S[b,a]:=l;
   end;

   writeln(Spfa(1,n));
  end;

  close(input);
  close(output);
 end.