1 #include <bits/stdc++.h>  2 using namespace std;  3 #define fr first  4 #define sc second  5 #define cl clear  6 #define BUG puts("here!!!")  7 #define W(a) while(a--)  8 #define pb(a) push_back(a)  9 #define Rint(a) scanf("%d", &a) 10 #define Rll(a) scanf("%lld", &a) 11 #define Rs(a) scanf("%s", a) 12 #define Cin(a) cin >> a 13 #define FRead() freopen("in", "r", stdin) 14 #define FWrite() freopen("out", "w", stdout) 15 #define Rep(i, len) for(int i = 0; i < (len); i++) 16 #define For(i, a, len) for(int i = (a); i < (len); i++) 17 #define Cls(a) memset((a), 0, sizeof(a)) 18 #define Clr(a, x) memset((a), (x), sizeof(a)) 19 #define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 20 #define lrt rt << 1 21 #define rrt rt << 1 | 1 22 #define pi 3.14159265359 23 #define RT return 24 #define lowbit(x) x & (-x) 25 #define onenum(x) __builtin_popcount(x) 26 typedef long long LL; 27 typedef long double LD; 28 typedef unsigned long long ULL; 29 typedef pair<int, int> pii; 30 typedef pair<string, int> psi; 31 typedef pair<LL, LL> pll; 32 typedef map<string, int> msi; 33 typedef vector<int> vi; 34 typedef vector<LL> vl; 35 typedef vector<vl> vvl; 36 typedef vector<bool> vb; 37  38 const int maxn = 1100; 39 const int maxm = 11000; 40 const int inf = 1000000000; 41 typedef struct Edge { 42   int u, v, w; 43   int next; 44   Edge() { next = -1; } 45 }Edge; 46  47 int n, m, s, t; 48 Edge edge[maxm]; 49 int head[maxn], ecnt; 50 int d[maxn]; 51 bool vis[maxn]; 52 int u, v, w; 53  54 int cnt, dhead[maxn]; 55 int cur[maxn], dd[maxn]; 56 Edge dedge[maxm]; 57 int S, T, N; 58  59 void adde(int u, int v, int w) { 60   edge[ecnt].u = u; edge[ecnt].v = v; edge[ecnt].w = w; 61   edge[ecnt].next = head[u]; head[u] = ecnt++; 62 } 63  64 void init() { 65   Clr(head, -1); ecnt = 0; Cls(vis); 66   Cls(edge); 67   Clr(dhead, -1); Cls(dedge); 68     cnt = 0; 69 } 70  71 void spfa(int s) { 72   queue<int> q; 73   Rep(i, n+1) d[i] = inf; 74   d[s] = 0; q.push(s); 75   vis[s] = 1; 76   while(!q.empty()) { 77     int u = q.front(); q.pop(); vis[u] = 0; 78     for(int i = head[u]; ~i; i=edge[i].next) { 79       int v = edge[i].v; 80       if(d[v] > d[u] + 1) { 81         d[v] = d[u] + 1; 82         if(!vis[v]) { 83           vis[v] = 1; 84           q.push(v); 85         } 86       } 87     } 88   } 89 } 90  91 void dadde(int u, int v, int w, int c1) { 92     dedge[cnt].u = u; dedge[cnt].v = v; dedge[cnt].w = w; 93     dedge[cnt].next = dhead[u]; dhead[u] = cnt++; 94     dedge[cnt].u = v; dedge[cnt].v = u; dedge[cnt].w = c1; 95     dedge[cnt].next = dhead[v]; dhead[v] = cnt++; 96 } 97  98 bool bfs(int s, int t, int n) { 99     queue<int> q;100     for(int i = 0; i < n; i++) dd[i] = inf;101     dd[s] = 0;102     q.push(s);103     while(!q.empty()) {104         int u = q.front(); q.pop();105         for(int i = dhead[u]; ~i; i = dedge[i].next) {106             if(dd[dedge[i].v] > dd[u] + 1 && dedge[i].w > 0) {107                 dd[dedge[i].v] = dd[u] + 1;108                 if(dedge[i].v == t) return 1;109                 q.push(dedge[i].v);110             }111         }112     }113     return 0;114 }115 116 int dinic(int s, int t, int n) {117     int st[maxn], top;118     int u;119     int flow = 0;120     while(bfs(s, t, n)) {121         for(int i = 0; i < n; i++) cur[i] = dhead[i];122         u = s; top = 0;123         while(cur[s] != -1) {124             if(u == t) {125                 int tp = inf;126                 for(int i = top - 1; i >= 0; i--) {127                     tp = min(tp, dedge[st[i]].w);128                 }129                 flow += tp;130                 for(int i = top - 1; i >= 0; i--) {131                     dedge[st[i]].w -= tp;132                     dedge[st[i] ^ 1].w += tp;133                     if(dedge[st[i]].w == 0) top = i;134                 }135                 u = dedge[st[top]].u;136             }137             else if(cur[u] != -1 && dedge[cur[u]].w > 0 && dd[u] + 1 == dd[dedge[cur[u]].v]) {138                 st[top++] = cur[u];139                 u = dedge[cur[u]].v;140             }141             else {142                 while(u != s && cur[u] == -1) {143                     u = dedge[st[--top]].u;144                 }145                 cur[u] = dedge[cur[u]].next;146             }147         }148     }149     return flow;150 }151 152 signed main() {153   //FRead();154   int ttt;155   Rint(ttt);156   W(ttt) {157     init();158     Rint(n); Rint(m);159     Rep(i, m) {160       Rint(u); Rint(v); Rint(w);161       adde(u,v,w); adde(v,u,w);162     }163     spfa(1);164     Rep(i, ecmt) {165       if(d[edge[i].v] == d[edge[i].u] + 1) {166         dadde(edge[i].u-1, edge[i].v-1, edge[i].w, 0);167       }168     }169     S = 0; T = n - 1; N = n;170     printf("%d\n", dinic(S, T, N));171   }172   RT 0;173 }