#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

int dp[][],pre[];

const int tmin=;

int maxflow;

void EK(int start,int end,int n){

    while(){

        queue<int>q;

        q.push();

       int  minflow=tmin;

        memset(pre,,sizeof(pre));

        while(!q.empty()){

            int u=q.front();

            q.pop();

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

                if(dp[u][i]>&&!pre[i]){

                    pre[i]=u;

                    q.push(i);

                }

            }

        }

        if(pre[end]==)

            break;

        for(int i=end;i!=start;i=pre[i]){

            minflow=min(dp[pre[i]][i],minflow);

        }

        for(int i=end;i!=start;i=pre[i]){

            dp[pre[i]][i]-=minflow;

            dp[i][pre[i]]+=minflow;

        }

        maxflow+=minflow;

    }

}

int main(){

   int count=;

   int n,m;

   int t;

   scanf("%d",&t);

   while(t--){

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

       memset(dp,,sizeof(dp));

       memset(pre,,sizeof(pre));

       count++;

       int u,v,w;

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

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

           dp[u][v]+=w;

       }

       maxflow=;

       EK(,n,n);

       printf("Case %d: %d\n",count,maxflow);

   }

   return ;

}