#include <iostream>

#include <queue>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = ;

const int INF = (<<);

int cap[maxn][maxn], flow[maxn][maxn];

int n;

int EdmondsKarp(int s, int t) {

    int p[maxn], a[maxn];

    queue<int> q;

    memset(flow, , sizeof(flow));

    int f = ;

    while(true) {

        memset(a, , sizeof(a));

        a[s] = INF;

        q.push(s);

        while(!q.empty()) { //BFS 找增广路

            int u = q.front(); q.pop();

            for(int v=; v<=n; v++) if(!a[v] && cap[u][v]>flow[u][v]){

                //找到新节点v

                p[v] = u; q.push(v);

                a[v] = min(a[u], cap[u][v]-flow[u][v]);

            }

        }

        if(a[t] == ) break;    //找不到，则当前流已经是最大流

        for(int u=t; u != s; u = p[u]) {    //从汇点往回走

            flow[p[u]][u] += a[t];  //更新正向流量

            flow[u][p[u]] -= a[t];  //更新反向流量

        }

        f += a[t];  //更新从 s 流出的流量

    }

    return f;

}

int main(){

    int T, m, u, v, c;

    scanf("%d", &T);

    for(int kase = ; kase <= T; kase++) {

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

        memset(cap, , sizeof(cap));

        for(int i=; i<m; i++) {

            scanf("%d %d %d", &u, &v, &c);

            cap[u][v] += c;

        }

        printf("Case %d: ", kase);

        int res = EdmondsKarp(, n);

        printf("%d\n", res);

    }

    return ;

}