1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 #define inf 0x3f3f3f3f
 7 const int maxn=1005;
 8 struct node{
 9     int to,nex,cap;
10 }e[maxn<<1];
11 int deep[maxn],head[maxn],vis[maxn];
12 int t,n,m,len;
13 void init()
14 {
15     len=0;
16     memset(deep,0,sizeof(deep));
17     memset(e,0,sizeof(e));
18     memset(head,-1,sizeof(head));
19 }
20 void add(int u,int v,int w)
21 {
22     e[len].to=v;
23     e[len].cap=w;
24     e[len].nex=head[u];
25     head[u]=len++;
26 }
27 bool bfs(int s,int t)
28 {
29     memset(vis,0,sizeof(vis));
30     queue<int> q;
31     while(!q.empty()) q.pop();
32     deep[s]=0;
33     vis[s]=1;
34     deep[t]=-1;
35     q.push(s);
36     while(!q.empty())
37     {
38         int u=q.front(); q.pop();
39         for(int i=head[u];i!=-1;i=e[i].nex)
40         {
41             int to=e[i].to;
42             if(e[i].cap<=0||vis[to]) continue;
43             vis[to]=1;
44             deep[to]=deep[u]+1;
45             q.push(to);
46         }
47     }
48     if(deep[t]==-1) return false;
49     else return true;
50 }
51 int dfs(int u,int t,int flow)
52 {
53     int res=0;
54     if(u==t||flow==0) return flow;
55     for(int i=head[u];i!=-1;i=e[i].nex)
56     {
57         int to=e[i].to;
58         if(deep[to]==deep[u]+1)
59         {
60             int f=dfs(to,t,min(flow,e[i].cap)); 
61             if(f<=0) continue;
62             e[i].cap-=f;
63             e[i^1].cap+=f;
64             flow-=f;
65             res+=f;
66             if(flow!=0) break; 
67         }
68     }
69     return res;
70 }
71 int Dinic(int s,int t)
72 {
73     int ans=0;
74     while(bfs(s,t))
75     {
76         ans+=dfs(s,t,inf);
77     }
78     return ans;
79 }
80 int main()
81 {
82     scanf("%d",&t);
83     for(int j=1;j<=t;j++)
84     {
85         init();
86         scanf("%d%d",&n,&m);
87         for(int i=1;i<=m;i++)
88         {
89             int u,v,w;
90             scanf("%d%d%d",&u,&v,&w);
91             add(u,v,w);
92             add(v,u,0);
93         }
94         printf("Case %d: %d\n",j,Dinic(1,n));
95     }
96 }