#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 4000
#define inf 1111111111
using namespace std;
struct Edge{
    int v,next,w;
}edge[200000];
int head[60000],en;
int gap[60000],h[60000];//gap霑吩クェ鬮伜コヲ逧?怏蜃?クェ?敬隸・轤ケ逧?ォ伜コヲ
int n,m,k,node,s,t,a,sum;
void addedge(int u,int v,int w)
{
    edge[en].v=v,edge[en].w=w;
    edge[en].next=head[u];
    head[u]=en++;
    swap(u,v);
    edge[en].v=v,edge[en].w=0;
    edge[en].next=head[u];
    head[u]=en++;
}
int dfs(int s,int t,int pos,int n,int cost)
{
    if(pos==t)
        return cost;
    int minh=n-1,lv=cost,d;
    for(int j=head[pos];j!=-1;j=edge[j].next)
    {
        int v=edge[j].v,w=edge[j].w;
        if(w>0)
        {
            if(h[v]+1==h[pos])
            {
                d=min(lv,w);
                d=dfs(s,t,v,n,d);
                edge[j].w-=d, edge[j^1].w+=d;
                lv-=d;
                if(h[s]>=n)    return cost-lv;
                if(lv==0)    break;
            }
            if(h[v]<minh)    minh=h[v];
        }
    }
    if(lv==cost)
    {
        gap[h[pos]]--;
        if(gap[h[pos]]==0)    h[s]=n;
        h[pos]=minh+1;
        gap[h[pos]]++;
    }
    return cost-lv;
}
int sap(int st,int ed,int n)
{
    int ret=0;
    memset(gap,0,sizeof(gap));
    memset(h,0,sizeof(h));
    gap[0]=n;
    while(h[st]<n)
        ret+=dfs(st,ed,st,n,inf);
    return ret;
}
int main()
{
    
    int ca,u,v,w;
    scanf("%d",&ca);
    for(int caa=1;caa<=ca;caa++)
    {
        scanf("%d%d",&n,&m);
        en=0;
        memset(head,-1,sizeof(head));
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
        }
        printf("Case %d: %d\n",caa,sap(1,n,n));
    }
    return 0;
}