#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c=getchar(); x=0;    while(!isdigit(c)) c=getchar();    while(isdigit(c)) {x=x*10+c-‘0‘; c=getchar();}}const int maxn = 30000 + 10;const int INF = 0x7FFFFFFF;struct Edge{    int from, to, cap, flow;    Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f){}};vector<Edge>edges;vector<int>G[maxn];bool vis[maxn];int d[maxn];int cur[maxn];int n, m, s, t;void init(){    for (int i = 0; i < maxn; i++)        G[i].clear();    edges.clear();}void AddEdge(int from, int to, int cap){    edges.push_back(Edge(from, to, cap, 0));    edges.push_back(Edge(to, from, 0, 0));    int w = edges.size();    G[from].push_back(w - 2);    G[to].push_back(w - 1);}bool BFS(){    memset(vis, 0, sizeof(vis));    queue<int>Q;    Q.push(s);    d[s] = 0;    vis[s] = 1;    while (!Q.empty())    {        int x = Q.front();        Q.pop();        for (int i = 0; i<G[x].size(); i++)        {            Edge e = edges[G[x][i]];            if (!vis[e.to] && e.cap>e.flow)            {                vis[e.to] = 1;                d[e.to] = d[x] + 1;                Q.push(e.to);            }        }    }    return vis[t];}int DFS(int x, int a){    if (x == t || a == 0)        return a;    int flow = 0, f;    for (int &i = cur[x]; i<G[x].size(); i++)    {        Edge e = edges[G[x][i]];        if (d[x]+1 == d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)        {            edges[G[x][i]].flow+=f;            edges[G[x][i] ^ 1].flow-=f;            flow+=f;            a-=f;            if(a==0) break;        }    }    if(!flow) d[x] = -1;    return flow;}int dinic(int s, int t){    int flow = 0;    while (BFS())    {        memset(cur, 0, sizeof(cur));        flow += DFS(s, INF);    }    return flow;}int h[maxn],sz,T;struct X{    int u,v,w,nx;}ee[maxn];int dis[maxn],flag[maxn];void add(int a,int b,int c){    ee[sz].u=a; ee[sz].v=b; ee[sz].w=c;    ee[sz].nx=h[a]; h[a]=sz++; }void spfa(){    for(int i=1;i<=n;i++) dis[i]=INF ,flag[i]=0;    dis[1]=0; queue<int>Q; Q.push(1); flag[1]=1;    while(!Q.empty())    {        int top=Q.front(); Q.pop(); flag[top]=0;        for(int i=h[top];i!=-1;i=ee[i].nx)        {            if(dis[top]+1<dis[ee[i].v])            {                dis[ee[i].v]=dis[top]+1;                if(flag[ee[i].v]==0)                {                    flag[ee[i].v]=1;                    Q.push(ee[i].v);                }            }        }    }}int main(){    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&n,&m); sz=0;        memset(h,-1,sizeof h);        for(int i=1;i<=m;i++)        {            int u,v,w; scanf("%d%d%d",&u,&v,&w);            add(u,v,w); add(v,u,w);        }        spfa();        init();        for(int i=0;i<sz;i++)        {            if(dis[ee[i].u]+1==dis[ee[i].v])            {                AddEdge(ee[i].u,ee[i].v,ee[i].w);            }        }        s=1; t=n;        printf("%d\n",dinic(s,t));    }    return 0;}