1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #include <vector>
  6 using namespace std;
  7 
  8 const int maxn = 20  << 1;
  9 const int INF = 1000000000;
 10 
 11 struct Edge
 12 {
 13     int from, to, cap, flow;
 14 };
 15 
 16 struct Dinic
 17 {
 18     int n, m, s, t;
 19     vector<Edge> edges;
 20     vector<int>G[maxn];
 21     bool vis[maxn];
 22     int d[maxn];
 23     int cur[maxn];
 24 
 25     void ClearAll(int n) {
 26         for(int i = 0; i <= n; i++) {
 27             G[i].clear();
 28         }
 29         edges.clear();
 30     }
 31 
 32     void AddEdge(int from, int to, int cap) {
 33         edges.push_back((Edge){from, to, cap, 0} );
 34         edges.push_back((Edge){to, from, 0, 0} );
 35         m = edges.size();
 36         G[from].push_back(m - 2);
 37         G[to].push_back(m - 1);
 38         //printf("%din end\n",m);
 39     }
 40 
 41     bool BFS()
 42     {
 43         memset(vis, 0, sizeof(vis) );
 44         queue<int> Q;
 45         Q.push(s);
 46         vis[s] = 1;
 47         d[s] = 0;
 48         while(!Q.empty() ){
 49             int x = Q.front(); Q.pop();
 50             for(int i = 0; i < G[x].size(); i++) {
 51                 Edge& e = edges[G[x][i]];
 52                 if(!vis[e.to] && e.cap > e.flow) {
 53                     vis[e.to] = 1;
 54                     d[e.to] = d[x] + 1;
 55                     Q.push(e.to);
 56                 }
 57             }
 58         }
 59         return vis[t];
 60     }
 61 
 62     int DFS(int x, int a) {
 63         if(x == t || a == 0) return a;
 64         int flow = 0, f;
 65         for(int& i = cur[x]; i < G[x].size(); i++) {
 66             Edge& e = edges[G[x][i]];
 67             if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
 68                 e.flow += f;
 69                 edges[G[x][i]^1].flow -= f;
 70                 flow += f;
 71                 a -= f;
 72                 if(a == 0) break;
 73             }
 74         }
 75         return flow;
 76     }
 77 
 78     int Maxflow(int s, int t) {
 79         this -> s = s; this -> t = t;
 80         int flow = 0;
 81         while(BFS()) {
 82             memset(cur, 0, sizeof(cur) );
 83             flow += DFS(s, INF);
 84         }
 85         return flow;
 86     }
 87 };
 88 
 89 Dinic g;
 90 
 91 int main()
 92 {
 93     int t;
 94     scanf("%d",&t);
 95     int n, m;
 96     int a, b, c;
 97     for(int kase = 1; kase <= t; kase++) {
 98         scanf("%d %d",&n, &m);
 99         g.ClearAll(maxn);
100         for(int i = 0;i < m; i++ ) {
101             scanf("%d %d %d",&a, &b, &c);
102             g.AddEdge(a, b, c);
103         }
104         printf("Case %d: %d\n",kase, g.Maxflow(1, n) );
105     }
106     return 0;
107 }