const inf=;

 var f:array[..,..] of longint;

     v:array[..] of longint;

     a,b,h:array[..] of longint;

     t,i,j,l,k,w,p,n,mx:longint;

 function min(a,b:longint):longint;

   begin

     if a>b then exit(b) else exit(a);

   end;

 begin

   readln(t);

   while t> do

   begin

     dec(t);

     readln(n);

     mx:=;

     fillchar(v,sizeof(v),);

     for i:= to n do

     begin

       readln(a[i],b[i],h[i]);

       v[a[i]]:=;

       v[b[i]]:=;

       if b[i]>mx then mx:=b[i];

     end;

     p:=;

     for i:= to mx do

       if v[i]= then

       begin

         inc(p);

         v[i]:=p;

       end;

     for i:= to n do

     begin

       a[i]:=v[a[i]];

       b[i]:=v[b[i]];

     end;

     h[]:=-inf;

     inc(p);

     for l:= to p do

       for i:= to p-l+ do

       begin

         j:=i+l-;

         w:=;

         for k:= to n do

           if (a[k]>i) and (b[k]<j) and (h[k]>h[w]) then w:=k;

         f[i,j]:=inf;

         if w= then f[i,j]:=

         else

           for k:=a[w] to b[w] do

             f[i,j]:=min(f[i,j],h[w]+f[i,k]+f[k,j]);

       end;

     writeln(f[,p]);

   end;

 end.