#include <stdio.h>#include <string.h>#include <stdlib.h>#include <queue>#include <math.h>#define inf 0x3f3f3f3fusing namespace std;int map[50][50],v[50],pre[1000];int n,m;int bfs(int s,int t){    memset(v,0,sizeof(v));    memset(pre,-1,sizeof(pre));    pre[s]=s;    queue<int>q;    q.push(s);    v[s]=1;    while(!q.empty())    {        int tt=q.front();        q.pop();        for(int i=1; i<=n; i++)        {            if(map[tt][i]&&v[i]==0)            {                v[i]=1;                pre[i]=tt;                q.push(i);                if(i==t)                {                    return 1;                }            }        }    }    return 0;}int EK(int s,int t){    int ans=0;    while(bfs(s,t)==1)    {        int min1=inf;        for(int i=t; i!=s; i=pre[i])        {            if(min1>map[pre[i]][i])            {                min1=map[pre[i]][i];            }        }        for(int i=t; i!=s; i=pre[i])        {            map[pre[i]][i]-=min1;            map[i][pre[i]]+=min1;        }        ans+=min1;    }    return ans;}int main(){    int T,x,y,z;    scanf("%d",&T);    for(int i=1; i<=T; i++)    {        scanf("%d%d",&n,&m);        memset(map,0,sizeof(map));        while(m--)        {            scanf("%d%d%d",&x,&y,&z);            map[x][y]+=z;        }        printf("Case %d: %d\n",i,EK(1,n));        EK(1,n);    }    return 0;}