#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
#define inf 2000000000
#define N 30
int map[N][N];
int pre[N],flow[N],start,end;
int bfs(){
int now,i;
memset(pre,-1,sizeof(pre));
flow[start]=inf;
queue<int>q;
while(!q.empty())
q.pop();
q.push(start);
while(!q.empty()) {
now=q.front();
q.pop();
for(i=1;i<=end;i++) {
if(i!=start&&pre[i]==-1&&map[now][i]) {
flow[i]=flow[now]<map[now][i]?flow[now]:map[now][i];
q.push(i);
pre[i]=now;
}
}
}
if(pre[end]==-1)return -1;
return flow[end];
}
int ek() {
int maxflow=0,step,pr,now;
while((step=bfs())!=-1) {
maxflow+=step;
now=end;
while(now!=start) {
pr=pre[now];
map[pr][now]-=step;
map[now][pr]+=step;
now=pr;
}
}
return maxflow;
}
int main(){
int n,m,a,b,c,t,num=0;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
start=1;end=n;
memset(map,0,sizeof(map));
while(m--) {
scanf("%d%d%d",&a,&b,&c);
map[a][b]+=c;
}
printf("Case %d: %d
",++num,ek());
}
return 0;
}