1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 5 #include<vector>
 6 using namespace std;
 7 
 8 struct Edge
 9 {
10     int from,to,cap,flow;
11 };
12 
13 const int inf=0x3f3f3f;
14 vector<Edge>edges;
15 vector<int>G[16];
16 int a[16],p[16];
17 int m,n;
18 
19 void init()
20 {
21     for(int i=1;i<=n;i++)G[i].clear();
22     edges.clear();
23     memset(p,0,sizeof(p));
24 }
25 
26 void addedge(int from,int to,int cap)
27 {
28     edges.push_back((Edge){from,to,cap,0});
29     edges.push_back((Edge){to,from,0,0});
30     int m=edges.size();
31     G[from].push_back(m-2);
32     G[to].push_back(m-1);
33 }
34 
35 int maxflow(int s,int t)
36 {
37     int flow=0;
38     while(1)
39     {
40         memset(a,0,sizeof(a));
41         queue<int>q;
42         q.push(s);
43         a[s]=inf;
44         while(!q.empty())
45         {
46             int x=q.front();
47             q.pop();
48             for(int i=0;i<G[x].size();i++)
49             {
50                 Edge& e=edges[G[x][i]];
51                 if(!a[e.to]&&e.cap>e.flow)
52                 {
53                     p[e.to]=G[x][i];
54                     a[e.to]=min(a[x],e.cap-e.flow);
55                     q.push(e.to);
56                 }
57             }
58             if(a[t])break;
59         }
60         if(!a[t])break;
61         for(int u=t;u!=s;u=edges[p[u]].from)
62         {
63             edges[p[u]].flow+=a[t];
64             edges[p[u]^1].flow-=a[t];
65         }
66         flow+=a[t];
67     }
68     return flow;
69 }
70 
71 int main()
72 {
73     int T;
74     scanf("%d",&T);
75     for(int t=1;t<=T;t++)
76     {
77         init();
78         printf("Case %d: ",t);
79         scanf("%d%d",&n,&m);
80         for(int i=0;i<m;i++)
81         {
82             int u,v,w;
83             scanf("%d%d%d",&u,&v,&w);
84             addedge(u,v,w);
85         }
86         int ans=maxflow(1,n);
87         printf("%d\n",ans);
88     }
89     return 0;
90 }