#include<stdio.h>

#include<string.h>

#include<stack>

#include<queue>

#include<vector>

#include<algorithm>

#define INF 0x7fffff

#define MAX 2100

using namespace std;

int ans,head[MAX];

int n,m;

int dis[MAX],vis[MAX];

int cur[MAX];

struct node

{

	int beg,end,cap,flow,next;

}edge[MAX];

void init()

{

	ans=0;

	memset(head,-1,sizeof(head));

}

void add(int u,int v,int w)

{

	edge[ans].beg=u;

	edge[ans].end=v;

	edge[ans].cap=w;

	edge[ans].flow=0;

	edge[ans].next=head[u];

	head[u]=ans++;

}

void getmap()

{

	int i,a,b,c;

	while(m--)

	{

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

		add(a,b,c);

		add(b,a,0);

	}

}

int bfs(int start,int over)

{

	int i,v;

	memset(dis,-1,sizeof(dis));

	memset(vis,0,sizeof(vis));

    queue<int>q;

    while(!q.empty())

        q.pop();

    q.push(start);

    vis[start]=1;

    dis[start]=0;

    while(!q.empty())

    {

    	int u=q.front();

    	q.pop();

    	for(i=head[u];i!=-1;i=edge[i].next)

    	{

    	    v=edge[i].end;

			if(!vis[v]&&edge[i].cap>edge[i].flow)

			{

				vis[v]=1;

				dis[v]=dis[u]+1;

				if(v==over)

				    return 1;

				q.push(v);

			}

    	}

    }

    return 0;

}

int dfs(int x,int a,int over)

{

	if(x==over||a==0)

	    return a;

	int flow=0,f;

	for(int& i=cur[x];i!=-1;i=edge[i].next)

	{

		if(dis[x]+1==dis[edge[i].end]&&(f=dfs(edge[i].end,min(a,edge[i].cap-edge[i].flow),over))>0)

		{

			edge[i].flow+=f;

			edge[i^1].flow-=f;

			flow+=f;

			a-=f;

			if(a==0) break;

		}

	}

	return flow;

}

int maxflow(int start,int over)

{

	int flow=0;

	while(bfs(start,over))

	{

		memcpy(cur,head,sizeof(head));

		flow+=dfs(start,INF,over);

	}

	return flow;

}

int main()

{

	int t,k,j,i;

	scanf("%d",&t);

	k=1;

	while(t--)

	{

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

		init();

		getmap();

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

		printf("%d\n",maxflow(1,n));

	}

	return 0;

}