#include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int n, m;

 int W[maxn][maxn], lft[maxn];

 int Lx[maxn], Ly[maxn];

 bool S[maxn], T[maxn];

 int slack[maxn];

 bool match(int u)

 {

     S[u] = true;

     for(int v = ; v <= n; v++) if(!T[v])

     {

         int t = Lx[u] + Ly[v] - W[u][v];

         if( == t)

         {

             T[v] = true;

             if(!lft[v] || match(lft[v]))

             {

                 lft[v] = u;

                 return true;

             }

         }

         else slack[v] = min(slack[v], t);

     }

     return false;

 }

 void update()

 {

     int a = ;

     for(int i = ; i <= n; i++) if(!T[i]) a = min(a, slack[i]);

     for(int i = ; i <= n; i++)

     {

         if(S[i]) Lx[i] -= a;

         if(T[i]) Ly[i] += a;

         else slack[i] -= a;

     }

 }

 void KM()

 {

     memset(lft, , sizeof(lft));

     memset(Lx, 0x80, sizeof(Lx));

     memset(Ly, , sizeof(Ly));

     for(int i = ; i <= n; i++)

         for(int j = ; j <= n; j++)

             Lx[i] = max(Lx[i], W[i][j]);

     for(int i = ; i <= n; i++)

     {

         memset(slack, 0x3f, sizeof(slack));

         for(;;)

         {

             memset(S, false, sizeof(S));

             memset(T, false, sizeof(T));

             if(match(i)) break;

             else update();

         }

     }

 }

 int main()

 {

     int T; scanf("%d", &T);

     while(T--)

     {

         scanf("%d%d", &n, &m);

         memset(W, 0x80, sizeof(W));

         for(int i = ; i < m; i++)

         {

             int u, v, d; scanf("%d%d%d", &u, &v, &d);

             W[u][v] = max(W[u][v], -d);

         }

         KM();

         int ans = ;

         for(int i = ; i <= n; i++) ans += W[lft[i]][i];

         printf("%d\n", -ans);

     }

     return ;

 }