#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

const int N = ;

const int INF = 0x7fffffff;

int flow[N];

int cap[N][N];

int pre[N];

queue<int>q;

int m, n;

int BFS(int src, int des)

{

    while (!q.empty()) q.pop();

    for (int i = ; i <= n; ++i) pre[i] = -;

    flow[src] = INF;

    pre[src] = ;

    q.push(src);

    while (!q.empty()) {

        int index = q.front();

        q.pop();

        if (index == des) break;

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

            if (pre[i] == - && cap[index][i] > ) {

                pre[i] = index;

                flow[i] = min(cap[index][i], flow[index]);

                q.push(i);

            }

        }

    }

    if (pre[des] == -) return -;

    return flow[des];

}

int maxFlow(int src, int des)

{

    int ans = ;

    int in = ;

    while ((in = BFS(src, des)) != -) {

        int k = des;

        while (k != src) {

            int last = pre[k];

            cap[last][k] -= in;

            cap[k][last] += in;

            k = last;

        }

        ans += in;

    }

    return ans;

}

int main()

{

    int t;

    int i, k;

    scanf("%d", &t);

    for (k = ; k <= t; ++k) {

        memset(cap, , sizeof cap);

        memset(flow, , sizeof flow);

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

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

            int a, b, c;

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

            cap[a][b] += c;

        }

        printf("Case %d: %d\n", k, maxFlow(, n));

    }

    return ;

}