#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int INF=<<;

 int cap[][],flow[][],n;

 int Edmonds_Karp(int s,int t)

 {

     int a[],p[];

     int f;

     queue<int>q;

     memset(flow,,sizeof(flow));

     f=;

     while()

     {

         memset(a,,sizeof(a));

         a[s]=INF;

         q.push(s);

         while(!q.empty())     //bfs找增广路

         {

             int u=q.front();

             q.pop();

             for(int v=; v<=n; v++)

             if(!a[v]&&cap[u][v]>flow[u][v])  //找到新节点v

             {

                 p[v]=u;   q.push(v);         //记录v的父亲，并加入FIFO队列

                 a[v]=min(a[u],cap[u][v]-flow[u][v]);  //s-v路径上的最小残量

             }

         }

         if(a[t]==) break;         //找不到，则当前流已经是最大流

         for(int u=t; u!=s; u=p[u])  //从汇点往回走

         {

             flow[p[u]][u]+=a[t];     //更新正向流量

             flow[u][p[u]]-=a[t];     //更新反向流量

         }

         f+=a[t];                    //更新从s流出的总流量

     }

     return f;

 }

 int main()

 {

     int t,m,x=;

     int u,v,w;

     scanf("%d",&t);

     while(t--)

     {

         memset(cap,,sizeof(cap));

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

         while(m--)

         {

             scanf("%d%d%d",&u,&v,&w);

             cap[u][v]+=w; //考虑重边

         }

         printf("Case %d: ",x++);

         printf("%d\n",Edmonds_Karp(,n));

     }

     return ;

 }