#include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int maxn = ;

 const int INF = ( << ) - ;

 struct Edge{

     int v,next,c;

 }e[maxn];

 int st,ed,lev[maxn],first[maxn],now[maxn],ecnt;

 int n,m;

 void init(int a,int b){

     st = a; ed = b;

     memset(first,-,sizeof(first));

     ecnt = ;

 }

 void addedges(int u,int v,int c){

     e[ecnt].next = first[u];

     e[ecnt].v = v;

     e[ecnt].c = c;

     first[u] = ecnt++;

     e[ecnt].next = first[v];

     e[ecnt].v = u;

     e[ecnt].c = ;

     first[v] = ecnt++;

 }

 bool bfs(){

     queue<int> q;

     while(!q.empty()) q.pop();

     q.push(st);

     memset(lev,-,sizeof(lev));

     lev[st] = ;

     while(!q.empty()){

         int x = q.front();q.pop();

         for(int i = first[x];~i;i = e[i].next){

             int v = e[i].v;

             if(lev[v] <  && e[i].c > ){

                 lev[v] = lev[x] + ;

                 q.push(v);

             }

         }

     }

     return lev[ed] != -;

 }

 int dfs(int p,int minf){

     if(p == ed || minf == ) return minf;

     for(int &i = now[p];~i;i = e[i].next){

         int v = e[i].v;

         if(lev[v] == lev[p] +  && e[i].c > ){

             int d = dfs(v,min(e[i].c,minf));

             if(d > ){

                 e[i].c -= d;

                 e[i^].c += d;

                 return d;

             }

         }

     }

     return ;

 }

 int dinic(){

     int max_flow = ,p1;

     while(bfs()){

         memcpy(now,first,sizeof(first));

         while((p1 = dfs(st,INF)) > )

         max_flow += p1;

     }

     return max_flow;

 }

 int main(){

     int T;

     int kase = ;

     scanf("%d",&T);

     while(T--){

         scanf("%d %d",&n,&m);

         init(,n);

         for(int i = ;i < m;i++){

             int a,b,c;

             scanf("%d %d %d",&a,&b,&c);

             addedges(a,b,c);

         }

         printf("Case %d: %d\n",++kase,dinic());

     }

     return ;

 }