#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1ll << ;

const int INF2 = 0x3f3f3f3f;

const int maxv = +;        //最大顶点数

const int maxn = maxv;

const int maxe = +;        //最大边数

ll dis[maxv];

int cnt[maxv];

bool inq[maxv];                //记录是否在队中

int head[maxv], id; //head2[maxv], cnt2;

int n, m;

struct Edge

{

    int to, w, next;

}edge[maxe];

inline void init()

{

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

    id=;

}

inline void addedge(int u, int v, int w, int id)

{

    edge[id].to = v;

    edge[id].w = w;

    edge[id].next = head[u];

    head[u] = id;

}

bool SPFA(int s)

{

    deque<int>q;

    memset(inq, false, sizeof(inq));

    memset(cnt, , sizeof(cnt));

    for (int i = ; i <= n; i++)  dis[i] = INF;

    dis[s] = ;

    inq[s] = true;

    q.push_back(s);

    while (!q.empty())

    {

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

        inq[u] = false;

        for (int i = head[u]; i != -; i = edge[i].next)

        {

            int v = edge[i].to, w = edge[i].w;

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

            {

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

                if (!inq[v])

                {

                    inq[v] = true;

                    //SLF优化

                    q.push_back(v);

                    if (++cnt[v] > n)  return false;

                    if (dis[q.back()] < dis[q.front()])

                    {

                        int k = q.back();

                        q.pop_back();

                        q.push_front(k);

                    }

                }

            }

        }

    }

    return true;

}

struct Edge2{

    int from, to, cap, flow;

    Edge2(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f){}

};

struct EdmondsKarp{

    int n, m;

    vector<Edge2>edges;      //边数的两倍

    vector<int>G[maxn];     //邻接表，G[i][j]表示结点i的第j条边在e数组中的序号

    int a[maxn];            //当起点到i的可改进量

    int p[maxn];        //最短树上p的入弧编号

    void init(int n)

    {

        for(int i = ;i <= n;i++)  G[i].clear();

        edges.clear();

    }

    void AddEdge(int from, int to, int cap)

    {

        edges.push_back(Edge2(from, to, cap, ));

        edges.push_back(Edge2(to, from, , ));

        m = edges.size();

        G[from].push_back(m-);

        G[to].push_back(m-);

    }

    ll Maxflow(int s, int t)

    {

        ll flow = ;

        for(;;)

        {

            memset(a, , sizeof(a));

            queue<int>Q;

            Q.push(s);

            a[s] = INF2;

            while(!Q.empty())

            {

                int x = Q.front(); Q.pop();

                for(int i = ;i < G[x].size();i++)

                {

                    Edge2& e = edges[G[x][i]];

                    if(!a[e.to] && e.cap > e.flow)

                    {

                        p[e.to] = G[x][i];

                        a[e.to] = min(a[x], e.cap-e.flow);

                        Q.push(e.to);

                    }

                }

                if(a[t])  break;

            }

            if(!a[t])  break;

            for(int u = t; u != s;u=edges[p[u]].from)

            {

                edges[p[u]].flow += a[t];

                edges[p[u]^].flow -= a[t];

            }

            flow += a[t];

        }

        return flow;

    }

}ek;

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        init();

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

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

        {

            int u, v, w;

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

            addedge(u, v, w, id++);

        }

        SPFA();

        ek.init(n);

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

        {

            for(int j = head[i]; j != -;j = edge[j].next)

            {

                int v = edge[j].to, w = edge[j].w;

                if(dis[v]-dis[i] == w)

                    ek.AddEdge(i, v, w);

            }

        }

        printf("%lld\n", ek.Maxflow(, n));

    }

    return ;

}