#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std ;

const int INF=0xfffffff ;

struct node{

    int s,t,cap,cost,nxt ;

}e[] ;

int sumflow ;

int n,m,cnt,head[],vis[],dis[],pre[] ;

void add(int s,int t,int cap,int cost)

{

    e[cnt].s=s ;e[cnt].t=t ;e[cnt].cap=cap ;e[cnt].cost=cost ;e[cnt].nxt=head[s] ;head[s]=cnt++ ;

    e[cnt].s=t ;e[cnt].t=s ;e[cnt].cap= ;e[cnt].cost=-cost ;e[cnt].nxt=head[t] ;head[t]=cnt++ ;

}

int spfa(int s,int t,int N)

{

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

        dis[i]=INF ;

    dis[s]= ;

    memset(vis,,sizeof(vis)) ;

    memset(pre,-,sizeof(pre)) ;

    vis[s]= ;

    queue <int> q ;

    q.push(s) ;

    while(!q.empty())

    {

        int u=q.front() ;

        q.pop() ;

        vis[u]= ;

        for(int i=head[u] ;i!=- ;i=e[i].nxt)

        {

            int tt=e[i].t ;

            if(e[i].cap && dis[tt]>dis[u]+e[i].cost)

            {

                dis[tt]=dis[u]+e[i].cost ;

                pre[tt]=i ;

                if(!vis[tt])

                {

                    vis[tt]= ;

                    q.push(tt) ;

                }

            }

        }

    }

    if(dis[t]==INF)return  ;

    return  ;

}

int MCMF(int s,int t,int N)

{

    int flow,minflow,mincost ;

    mincost=flow= ;

    while(spfa(s,t,N))

    {

        minflow=INF ;

        for(int i=pre[t] ;i!=- ;i=pre[e[i].s])

            minflow=min(minflow,e[i].cap) ;

        flow+=minflow ;

        for(int i=pre[t] ;i!=- ;i=pre[e[i].s])

        {

            e[i].cap-=minflow ;

            e[i^].cap+=minflow ;

        }

        mincost+=dis[t]*minflow ;

    }

    sumflow=flow ;//最大流

    return mincost ;

}

int main()

{

    int t ;

    scanf("%d",&t) ;

    while(t--)

    {

        cnt= ;

        memset(head,-,sizeof(head)) ;

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

        int ss= ;

        int st=*n+ ;

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

        {

            int s,t,v ;

            scanf("%d%d%d",&s,&t,&v) ;

            add(s,t+n,,v) ;

        }

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

            add(,i,,) ;

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

            add(i,st,,) ;

        int ans=MCMF(ss,st,st+) ;

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

    }

    return  ;

}