program project1;
var a:array[0..201,0..201] of longint;
    d:array[0..201] of longint;
    v:array[0..201] of boolean;
    t,n,m:longint;
procedure init;
begin
     assign(input,'hardest.in');reset(input);
     assign(output,'hardest.out');rewrite(output);
     read(t);
end;
function dijkstra(s:longint):longint;
var i,u,min,j:longint;
begin
     fillchar(v,sizeof(v),0);
     v[s]:=true;
     for i:=1 to n do d[i]:=a[s,i];
     for i:=1 to n-1 do
     begin
          min:=999999999;u:=-1;
          for j:=1 to n do if (not v[j])and(d[j]<min) then
          begin
               min:=d[j];
               u:=j;
          end;
          if u=-1 then break;
          v[u]:=true;
          for j:=1 to n do if (not v[j]) and (d[j]>d[u]+a[u,j]) then
              d[j]:=d[u]+a[u,j];
     end;
     if d[n]=999999999 then exit(-1) else exit(d[n]);
end;
procedure main;
var tt,i,j,x,y,w:longint;
begin
     for tt:=1 to t do
     begin
          read(n,m);
          for i:=1 to n do
              for j:=1 to n do
                  a[i,j]:=999999999;
          for i:=1 to m do
          begin
               read(x,y,w);
               if a[x,y]>w then
               a[x,y]:=w;
               a[y,x]:=a[x,y];
          end;
          for i:=1 to n do a[i,i]:=0;
          writeln(dijkstra(1));
     end;
     close(input);
     close(output);
end;
begin
     init;
     main;
end.