#include <bits/stdc++.h>using namespace std;
#define MAXN 20100
#define MAXM 20100
bool visited[MAXN]; //标记数组
long long dist[MAXN]; //源点到顶点i的最短距离
long long path[MAXN]; //记录最短路的路径
long long enqueue_num[MAXN]; //记录入队次数
long long vertex_num; //顶点数
long long edge_num; //边数
long long source; //源点
struct Edge {
long long to, next, cap, flow;
} edge[MAXM];
long long head[MAXN];
long long tot;
long long gap[MAXN], dep[MAXN], cur[MAXN];
void init() {
tot = 0;
memset(head, -1, sizeof(head));
}
void addedge(long long u, long long v, long long w) {
edge[tot].to = v;
edge[tot].cap = w;
edge[tot].next = head[u];
edge[tot].flow = 0;
head[u] = tot++;
}
bool SPFA() {
memset(visited, 0, sizeof(visited));
memset(enqueue_num, 0, sizeof(enqueue_num));
for (long long i = 0; i < vertex_num; i++) {
dist[i] = __LONG_LONG_MAX__;
path[i] = source;
}
queue<long long> Q;
Q.push(source);
dist[source] = 0;
visited[source] = true;
enqueue_num[source]++;
while (!Q.empty()) {
long long u = Q.front();
Q.pop();
visited[u] = 0;
for (long long curnode = head[u]; curnode != -1; curnode = edge[curnode].next) {
if (dist[u] + edge[curnode].cap < dist[edge[curnode].to]) {
dist[edge[curnode].to] = dist[u] + edge[curnode].cap;
path[edge[curnode].to] = u;
if (!visited[edge[curnode].to]) {
Q.push(edge[curnode].to);
enqueue_num[edge[curnode].to]++;
if (enqueue_num[edge[curnode].to] >= vertex_num)
return false;
visited[edge[curnode].to] = 1;
}
}
}
}
return true;
}
long long Q[MAXN];
void BFS(long long start, long long end) {
memset(dep, -1, sizeof(dep));
memset(gap, 0, sizeof(gap));
gap[0] = 1;
long long front = 0, rear = 0;
dep[end] = 0;
Q[rear++] = end;
while (front != rear) {
long long u = Q[front++];
for (long long i = head[u]; i != -1; i = edge[i].next) {
long long v = edge[i].to;
if (dep[v] != -1)
continue;
Q[rear++] = v;
dep[v] = dep[u] + 1;
gap[dep[v]]++;
}
}
}
long long S[MAXN];
long long sap(long long start, long long end, long long N) {
BFS(start, end);
memcpy(cur, head, sizeof(head));
long long top = 0;
long long u = start;
long long ans = 0;
while (dep[start] < N) {
if (u == end) {
long long Min = __LONG_LONG_MAX__;
long long inser;
for (long long i = 0; i < top; i++) {
if (Min > edge[S[i]].cap - edge[S[i]].flow) {
Min = edge[S[i]].cap - edge[S[i]].flow;
inser = i;
}
}
for (long long i = 0; i < top; i++) {
edge[S[i]].flow += Min;
edge[S[i] ^ 1].flow -= Min;
}
ans += Min;
top = inser;
u = edge[S[top] ^ 1].to;
continue;
}
bool flag = false;
long long v;
for (long long i = cur[u]; i != -1; i = edge[i].next) {
v = edge[i].to;
if (edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u]) {
flag = true;
cur[u] = i;
break;
}
}
if (flag) {
S[top++] = cur[u];
u = v;
continue;
}
long long Min = N;
for (long long i = head[u]; i != -1; i = edge[i].next)
if (edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) {
Min = dep[edge[i].to];
cur[u] = i;
}
gap[dep[u]]--;
if (!gap[dep[u]])
return ans;
dep[u] = Min + 1;
gap[dep[u]]++;
if (u != start)
u = edge[S[--top] ^ 1].to;
}
return ans;
}
long long n, m;
int a[MAXN], b[MAXN], c[MAXN];
void reISAP() {
init();
for (int i = 0; i < m; i++) {
if (c[i] == dist[b[i]] - dist[a[i]]) {
addedge(a[i], b[i], c[i]);
addedge(b[i], a[i], 0);
}
}
}
int main() {
#ifdef ACM_LOCAL
freopen("./in.txt", "r", stdin);
freopen("./out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
long long t;
cin >> t;
while (t--) {
cin >> n >> m;
source = 1;
vertex_num = n + 1;
init();
for (long long i = 0; i < m; i++) {
cin >> a[i] >> b[i] >> c[i];
addedge(a[i], b[i], c[i]);
}
if (!SPFA()) {
cout << '0' << endl;
continue;
}
reISAP();
cout << sap(1, n, n) << endl;
}
return 0;
}
