#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<queue>

#include<cstdio>

#include<stack>

#include<cmath>

#include<iostream>

#define ll long long

#define lowbit(x) x&(-x)

using namespace std;

const int maxn=;

const int maxm=;

const ll inf=1e18;

struct node{

    int u,v,nxt;

    ll w;

}e[*maxm],e2[*maxm],e3[*maxm];

int h[maxn],h2[maxn],h3[maxn],depth[maxn];

ll d[maxn],d2[maxn];

bool vis[maxn];

int n,m,st,ed,cnt,cnt2,cnt3;

void init()

{

    memset(h,-,sizeof(h));

    memset(h2,-,sizeof(h2));

    memset(h3,-,sizeof(h3));

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

        d[i]=d2[i]=inf;

    cnt=cnt2=cnt3=;

}

void add(int u,int v,ll w)//正向建边

{

    e[cnt].u=u,e[cnt].v=v,e[cnt].w=w;

    e[cnt].nxt=h[u];h[u]=cnt++;

}

void add2(int u,int v,ll w)//反向建边

{

    e2[cnt2].u=u,e2[cnt2].v=v,e2[cnt2].w=w;

    e2[cnt2].nxt=h2[u],h2[u]=cnt2++;

}

void add3(int u,int v,ll w)//重新建边

{

    e3[cnt3].u=u,e3[cnt3].v=v,e3[cnt3].w=w;

    e3[cnt3].nxt=h3[u],h3[u]=cnt3++;

}

bool spfa()//求每点到1的最短距离

{

    queue<int> q;

    memset(vis,,sizeof(vis));

    d[st]=;

    vis[st]=;

    q.push(st);

    while(!q.empty())

    {

        int u=q.front();q.pop();

        vis[u]=;

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

        {

            int v=e[i].v;

            ll  w=e[i].w;

            if(d[v]>d[u]+w)

            {

                d[v]=d[u]+w;

                if(!vis[v])

                {

                    vis[v]=;

                    q.push(v);

                }

            }

        }

    }

    return d[n]==inf;

}

void re_spfa()//求每点到n的最短距离

{

    queue<int> q;

    memset(vis,,sizeof(vis));

    d2[ed]=;

    vis[ed]=;

    q.push(ed);

    while(!q.empty())

    {

        int u=q.front();q.pop();

        vis[u]=;

        for(int i=h2[u];i!=-;i=e2[i].nxt)

        {

            int v=e2[i].v;

            ll  w=e2[i].w;

            if(d2[v]>d2[u]+w)

            {

                d2[v]=d2[u]+w;

                if(!vis[v])

                {

                    vis[v]=;

                    q.push(v);

                }

            }

        }

    }

}

void create_map()//重新建边

{

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

    {

        int u=e[i].u;

        int v=e[i].v;

        ll  w=e[i].w;

        if((d[u]+d2[v]+w==d[ed])&&(d[u]<inf&&d2[v]<inf))

        {//最短路核心边

            add3(u,v,w);

            add3(v,u,);

        }

    }

}

bool bfs(){//dinic分层

    queue<int> que;

    memset(depth,,sizeof(depth));

    que.push(st);

    depth[st]=;

    while(!que.empty()){

        int u=que.front();

        que.pop();

        if(u==ed)

            return true;

        for(int i=h3[u];i!=-;i=e3[i].nxt){

            int v=e3[i].v;

            ll  w=e3[i].w;

            if(!depth[v]&&w){

                depth[v]=depth[u]+;

                que.push(v);

            }

        }

    }

    return false;

}

ll dfs(int u,ll dis)

{

    if(u==ed)

        return dis;

    ll res=;

    for(int i=h3[u];i!=-;i=e3[i].nxt)

    {

        int v=e3[i].v;

        ll  w=e3[i].w;

        if((depth[v]==depth[u]+)&&w)

        {

            ll di=dfs(v,min(w,dis-res));

            e3[i].w-=di;

            e3[i^].w+=di;

            res+=di;

            if(res==dis)

                return dis;

        }

    }

    return res;

}

void dinic()//dinic求最小割

{

    ll ans=;

    while(bfs())

    {

        ans+=dfs(st,inf);

    }

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

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

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

        st=,ed=n;

        init();

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

        {

            int u,v;ll w;

            scanf("%d%d%lld",&u,&v,&w);

            add(u,v,w);

            add2(v,u,w);

        }

        if(spfa())//特判，没有最短路

            printf("0\n");

        else

        {

            re_spfa();

            create_map();

            dinic();

        }

    }

    return ;

}