#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<queue>
#define ll long long
#define mx 0x3f3f3f3f
using namespace std;
int flow[205][205],cap[205][205];//flow当前流量，cap总容量
int f[205],vis[205];//f[i]最小残量=cap-flow,vis[i]标记i节点的上一个最小残量所在的位置
int mx_flow;//最大流量，所有增广路最小残量之和
void bfs(int n)
{
    queue<int>p;
    mx_flow=0;
    int flag=0;
    memset(flow,0,sizeof(flow));
    while(flag==0)
    {
        memset(f,0,sizeof(f));
        memset(vis,0,sizeof(vis));
        f[1]=mx,vis[1]=-1;//初始化源点
        p.push(1);
        while(!p.empty())//bfs找增广路
        {
            int now=p.front();
            p.pop();
            for(int i=1;i<=n;i++)
            {
                if(!f[i]&&flow[now][i]<cap[now][i])
                {
                    f[i]=min(f[now],cap[now][i]-flow[now][i]);//取最小残量
                    vis[i]=now;
                    p.push(i);
                }
            }
        }
        if(f[n]==0)//容量-流量==0，一条增广路寻找结束
            flag=1;
        mx_flow+=f[n];
        int pos=n;//从汇点开始更新流量
        while(!flag&&pos!=1)
        {
            flow[vis[pos]][pos]+=f[n];//正向更新流量
            flow[pos][vis[pos]]-=f[n];//反向更新流量
            pos=vis[pos];
        }
    }
}

int main()
{
    int t,n,m,cnt=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);//n是顶点数，m是边数
        memset(cap,0,sizeof(cap));
        for(int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            cap[x][y]+=z;
        }
        bfs(n);
        printf("Case %d: %d\n",++cnt,mx_flow);
    }
}