5651번: 완전 중요한 간선 ↗

#include <bits/stdc++.h>

#define for1(s,n) for(int i = s; i < n; i++)
#define for1j(s,n) for(int j = s; j < n; j++)
#define foreach(k) for(auto i : k)
#define foreachj(k) for(auto j : k)
#define pb(a) push_back(a)
#define sz(a) a.size()

#define MAX_V 330
#define SRC 1
#define INF (ll)1e18

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector <int> iv1;
typedef vector <vector<int>> iv2;
typedef vector <ll> llv1;
typedef unsigned int uint;
typedef vector <ull> ullv1;
typedef vector <vector <ull>> ullv2;

ll SINK;

struct Edge {
    ll v, capacity, rev, chk;
    Edge(ll v, ll capacity, ll rev, ll chk): v(v), capacity(capacity), rev(rev), chk(chk) {}
};

vector<Edge> vt[MAX_V];
ll level[MAX_V];
ll work[MAX_V];
ll d[MAX_V][MAX_V];

void clearEdge() {
    for1(0, MAX_V) {
        vt[i].clear();
    }
}

void addEdge(ll start, ll end, ll capacity) {
    vt[start].emplace_back(end, capacity, (ll)vt[end].size(), 1ll);
    vt[end].emplace_back(start, 0, (ll)vt[start].size()-1, 0ll);
}

// 레벨 그래프 만드는 BFS
bool bfs() {
    memset(level, -1, sizeof(level));        //레벨 그래프 초기화
    queue <ll> q;
    level[SRC] = 0;
    q.push(SRC);

    while(!q.empty()){
        int here = q.front(); q.pop();
        for (auto i : vt[here]) {
            ll there = i.v;
            if(level[there] == -1 && i.capacity > 0) {
                level[there] = level[here] + 1;
                q.push(there);
            }
        }
    }
    return level[SINK] != -1;
}


ll dfs(ll here, ll crt_capacity) {
    if(here == SINK) return crt_capacity;

    for(ll &i = work[here]; i < vt[here].size(); i++) {
        ll there = vt[here][i].v;
        ll capacity = vt[here][i].capacity;

        if(level[here] + 1 == level[there] && capacity > 0) {
            ll next_capacity = dfs(there, min(crt_capacity, capacity));

            if(next_capacity > 0) {
                vt[here][i].capacity -= next_capacity;
                vt[there][vt[here][i].rev].capacity += next_capacity;
                return next_capacity;
            }
        }
    }
    return 0;
}

ll dinic() {
    ll ret = 0;
    while(bfs()) {
        memset(work, 0, sizeof(work));

        while(1) {
            ll flow = dfs(SRC, INF);
            if(!flow) break;
            ret += flow;
        }
    }
    return ret;
}

ll tc;
ll n,m;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> tc;
    while(tc--) {
        clearEdge();
        cin >> n >> m;
        SINK = n;
        for1(0, m) {
            ll a, b, c;
            cin >> a >> b >> c;
            addEdge(a,b,c);
        }
        ll ret = dinic();
        for1(0, n+1)
            for1j(0, n+1)
                d[i][j] = 0;
        for1(0, n+1) {
            for(auto j : vt[i]) {
                if(j.capacity > 0) d[i][j.v] = 1;
            }
        }
        for1(1, n+1) {
            for1j(1, n+1) {
                for(int k = 1; k <= n; k++) {
                    if(d[j][i] && d[i][k]) d[j][k] = 1;
                }
            }
        }


        ll ans = 0;
        for1(1, n+1) {
            for(auto j : vt[i]) {
                if(!d[i][j.v] && j.chk) {
                    ans++;
                }
            }
        }
        cout << ans << "\n";
    }
    
}