/* 3549 */

 #include <iostream>

 #include <string>

 #include <map>

 #include <queue>

 #include <set>

 #include <stack>

 #include <vector>

 #include <deque>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <ctime>

 #include <cstring>

 #include <climits>

 #include <cctype>

 #include <cassert>

 #include <functional>

 using namespace std;

 #define rep(i, a, n)     for (int i=a;i<n;++i)

 #define per(i, a, n)     for (int i=n-1;i>=a;--i)

 #define pb                 push_back

 #define mp                 make_pair

 #define all(x)             (x).begin(),(x).end()

 #define SZ(x)             ((int)(x).size())

 #define lson            l, mid, rt<<1

 #define rson            mid+1, r, rt<<1|1

 const int maxn = ;

 int F[maxn][maxn];

 int P[maxn], a[maxn];

 int n, m, ans;

 int s, t;

 bool bfs() {

     int u, v;

     queue<int> Q;

     memset(a, , sizeof(a));

     a[s] = INT_MAX;

     Q.push(s);

     P[s] = s;

     while (!Q.empty()) {

         u = Q.front();

         Q.pop();

         for (v=; v<=n; ++v) {

             if (!a[v] && F[u][v]) {

                 P[v] = u;

                 Q.push(v);

                 a[v] = min(a[u], F[u][v]);

             }

         }

     }

     return a[t] == ;

 }

 void Edmonds_Karp() {

     int u, v;

     s = ;

     t = n;

     ans = ;

     while (true) {

         if (bfs())

             break;

         for (u=t; u!=s; u=P[u]) {

             F[u][P[u]] += a[t];

             F[P[u]][u] -= a[t];

         }

         ans += a[t];

     }

 }

 int main() {

     int i, j, k;

     int t, tt;

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

         freopen("data.out", "w", stdout);

     #endif

     scanf("%d", &tt);

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

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

         memset(F, , sizeof(F));

         while (m--) {

             scanf("%d %d %d", &i, &j, &k);

             F[i][j] += k;

         }

         Edmonds_Karp();

         printf("Case %d: %d\n", t, ans);

     }

     #ifndef ONLINE_JUDGE

         printf("time = %d.\n", (int)clock());

     #endif

     return ;

 }