program fall;
type pt=^dy;
     dy=record
     link,data:longint;
     nct:pt;
     end;
var a:array [1..222] of dy;
    head,k,n,m,tail,now,i,x,y,z,t,ts,te:longint;
    p:pt;
    dist:array [1..222] of longint;
    v:array [1..222] of boolean;
    q:array [1..500000] of longint;
begin
 assign(input,'hardest.in');
 assign(output,'hardest.out');
 reset(input);
 reset(output);
 readln(t);
 for k:=1 to t do
  begin
   readln(n,m);
   ts:=1; te:=n;
   for i:=1 to n do a[i].nct:=nil;
   for i:=1 to m do
    begin
     read(x,y,z);
     new(p); p^.link:=y; p^.data:=z; p^.nct:=a[x].nct; a[x].nct:=p;
    end;
   fillchar(dist,sizeof(dist),$7f); fillchar(v,sizeof(v),true);
   head:=1; tail:=1; q[1]:=ts; v[ts]:=false; dist[ts]:=0;
   while head<=tail do
    begin
     now:=q[head]; p:=a[now].nct;
     while p<>nil do
      begin
       if dist[p^.link]>dist[now]+p^.data then
       begin
        dist[p^.link]:=dist[now]+p^.data;
        if v[p^.link] then
         begin inc(tail); q[tail]:=p^.link; v[p^.link]:=false; end;
       end;
       p:=p^.nct;
      end;
     inc(head); v[now]:=true;
    end;
   writeln(dist[te]);
  end;
 close(input);
 close(output);
end.