#include <iostream>
#include <queue>
#define num 20
#define max 10000
#define min(a, b) a > b ? b : a
using namespace std;

int n, m, t, f, map[num][num], pre[num];
bool hash[num];

void init()
{
     f = 0;
     memset(map, 0, sizeof(map));
     cin >> n >> m;
     for (int i = 0; i < m; ++ i)
     {
          int a, b, c;
          cin >> a >> b >> c;
          map[a][b] = c;
     }
}

void max_flow()
{
     while (1)
     {
          queue<int> q;
          memset(hash, false, sizeof(hash));
          memset(pre, 0, sizeof(pre));
          q.push(1);
          hash[1] = true;
          while (!q.empty())
          {
               int cur = q.front();
               q.pop();
               if (cur == n)   break;
               for (int i = 1; i <= n; ++ i)
               {
                    if (!hash[i] && map[cur][i] > 0)
                    {
                         hash[i] = true;
                         pre[i] = cur;
                         q.push(i);
                    }
               }
          }
          if (!hash[n])    break;
          int low = max;
          for (int i = n; i != 1; i = pre[i])
          {
               low = min(low, map[pre[i]][i]);
          }
          for (int i = n; i != 1; i = pre[i])
          {
               map[pre[i]][i] -= low;
               map[i][pre[i]] += low;
          }
          f += low;
     }
}

int main()
{
     cin >> t;
     for (int i = 1; i <= t; ++ i)
     {
          init();
          max_flow();
          cout << "Case " << i << ": " << f << endl;
     }
     return 0;
}