view code//hdu 3987
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<59;
const ll E = 100001;
const int N = 1010;
int _, n, m, pre[N], cur[N], d[N], s, t;
bool vis[N];
struct edge
{
int u, v;
ll cap, flow;
int next;
edge() {}
edge(int u, int v, ll w, ll f, int p):u(u),v(v),cap(w),flow(f),next(p) {}
}e[N*400];
int ecnt;
void addedge(int u, int v, int w)
{
e[ecnt] = edge(u, v, w*E+1, 0, pre[u]);
pre[u] = ecnt++;
e[ecnt] = edge(v, u, 0, 0, pre[v]);
pre[v] = ecnt++;
}
bool BFS()
{
memset(vis, 0, sizeof(vis));
queue<int >q;
q.push(s);
d[s] = 0;
vis[s] = 1;
while(!q.empty())
{
int x = q.front(); q.pop();
for(int i=pre[x]; ~i; i = e[i].next)
{
int v =e[i].v;
if(!vis[v] && e[i].cap>e[i].flow)
{
d[v] = d[x] + 1;
vis[v] = 1;
q.push(v);
}
}
}
return vis[t];
}
ll DFS(int x, ll c)
{
if(x==t || c==0) return c;
ll flow = 0, f;
for(int &i = cur[x]; ~i; i=e[i].next)
{
int v = e[i].v;
if(d[x] + 1 == d[v] && (f=DFS(v, min(c, e[i].cap-e[i].flow)))>0)
{
e[i].flow += f;
e[i^1].flow -= f;
flow += f;
c -= f;
if(c==0) break;
}
}
return flow;
}
ll Maxflow()
{
s = 0, t = n-1;
ll flow = 0;
while(BFS())
{
for(int i=s; i<=t; i++) cur[i] = pre[i];
flow += DFS(s, INF);
}
return flow;
}
void solve()
{
scanf("%d%d", &n, &m);
int u, v, w, flag;
memset(pre, -1, sizeof(pre));
ecnt = 0;
for(int i=0; i<m; i++)
{
scanf("%d%d%d%d", &u, &v, &w, &flag);
addedge(u, v, w);
if(flag) addedge(v, u, w);
}
static int cas=1;
printf("Case %d: ", cas++);
cout<<Maxflow()%E<<endl;
}
int main()
{
// freopen("in.txt", "r", stdin);
cin>>_;
while(_--) solve();
return 0;
}
/*
题意：
求最小割，但因为最小割是不唯一的，题目要求得到最小割的条件下，使得割边最少，输出最少割边数
思路：
有两种做法，但本质是一样的
第一种：
建边的时候每条边权 w = w * (E + 1) + 1;
这样得到最大流 maxflow / (E + 1) ，最少割边数 maxflow % (E + 1)
道理很简单，如果原先两类割边都是最小割，那么求出的最大流相等
但边权变换后只有边数小的才是最小割了
乘（E+1）是为了保证边数叠加后依然是余数，不至于影响求最小割的结果
第二种：
建图，得到最大流后，图中边若满流，说明该边是最小割上的边
再建图，原则：满流的边改为容量为 1 的边，未满流的边改为容量 INF 的边，然后最大流即答案
*/
