#include<iostream>

 #include<cstring>

 #include<string>

 #include<algorithm>

 #include<queue>

 using namespace std;

 int n, m, flow;

 int vis[];

 //路径记录

 int pre[];

 //邻接表

 int G[][];

 void Maxflow()

 {

     for (;;)

     {

         memset(vis, , sizeof(vis));

         memset(pre, , sizeof(pre));

         queue<int> q;

         q.push();

         vis[] = ;

         while (!q.empty())

         {

             int x = q.front();

             q.pop();

             //到达终点

             if (x == n)  break;

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

             {

                 if (!vis[i] && G[x][i] > )

                 {

                     vis[i] = ;

                     q.push(i);

                     //记录好路径

                     pre[i] = x;

                 }

             }

         }

         //没有找到增广路

         if (!vis[n])  break;

         int _min = ;

         for (int i = n; i != ; i = pre[i])

             _min = min(_min, G[pre[i]][i]);

         for (int i = n; i != ; i = pre[i])

         {

             G[i][pre[i]] += _min;

             G[pre[i]][i] -= _min;

         }

         flow += _min;

     }

     return;

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     int T;

     int u, v, w;

     cin >> T;

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

     {

         cin >> n >> m;

         memset(G, , sizeof(G));

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

         {

             cin >> u >> v >> w;

             G[u][v] += w;

         }

         flow = ;

         Maxflow();

         cout << "Case " << kase << ": " << flow << endl;

     }

 }