题目大意：求割边最少的最小割。

题目分析：将容量乘上一个比较大的常数并加一来代替原来的容量，这样跑出来的最大流除以常数就是最小割容量，对常数取模就是最少割边数。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define RPEF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define clear( a , x ) memset ( a , x , sizeof a )
#define copy( a , x ) memcpy ( a , x , sizeof a )

typedef long long LL ;

const int MAXN = 1005 ;
const int MAXE = 1000000 ;
const int MAXQ = 1000000 ;
const LL INF = 1e15 ;

struct Edge {
	int v , n ;
	LL c ;
	Edge ( int var = 0 , LL cap = 0 , int next = 0 ) :
		v ( var ) , c ( cap ) , n ( next ) {}
} ;

struct netWork {
	Edge edge[MAXE] ;
	int adj[MAXN] , cntE ;
	int cur[MAXN] , d[MAXN] , num[MAXN] , pre[MAXN] ;
	bool vis[MAXN] ;
	int Q[MAXQ] , head , tail ;
	int s , t , nv ;
	LL flow ;
	
	void init () {
		cntE = 0 ;
		clear ( adj , -1 ) ;
	}
	
	void addedge ( int u , int v , LL c , LL rc = 0 ) {
		edge[cntE] = Edge ( v ,  c , adj[u] ) ;
		adj[u] = cntE ++ ;
		edge[cntE] = Edge ( u , rc , adj[v] ) ;
		adj[v] = cntE ++ ;
	}
	
	void rev_Bfs () {
		clear ( vis , 0 ) ;
		clear ( num , 0 ) ;
		d[t] = 0 ;
		vis[t] = 1 ;
		head = tail = 0 ;
		Q[tail ++] = t ;
		num[0] = 1 ;
		while ( head != tail ) {
			int u = Q[head ++] ;
			for ( int i = adj[u] ; ~i ; i = edge[i].n ) {
				int v = edge[i].v ;
				if ( vis[v] )
					continue ;
				vis[v] = 1 ;
				d[v] = d[u] + 1 ;
				++ num[d[v]] ;
				Q[tail ++] = v ;
			}
		}
	}
	
	LL ISAP () {
		copy ( cur , adj ) ;
		rev_Bfs () ;
		flow = 0 ;
		int i , u = pre[s] = s ;
		while ( d[s] < nv ) {
			if ( u == t ) {
				LL f = INF ;
				int pos ;
				for ( i = s ; i != t ; i = edge[cur[i]].v )
					if ( f > edge[cur[i]].c )
						f = edge[cur[i]].c , pos = i ;
				for ( i = s ; i != t ; i = edge[cur[i]].v )
					edge[cur[i]].c -= f , edge[cur[i] ^ 1].c += f ;
				u = pos ;
				flow += f ;
			}
			for ( i = cur[u] ; ~i ; i = edge[i].n )
				if ( edge[i].c && d[u] == d[edge[i].v] + 1 )
					break ;
			if ( ~i ) {
				cur[u] = i ;
				pre[edge[i].v] = u ;
				u = edge[i].v ;
			}
			else {
				if ( 0 == ( -- num[d[u]] ) )
					break ;
				int mmin = nv ;
				for ( i = adj[u] ; ~i ; i = edge[i].n )
					if ( edge[i].c && mmin > d[edge[i].v] )
						cur[u] = i , mmin = d[edge[i].v] ;
				d[u] = mmin + 1 ;
				++ num[d[u]] ;
				u = pre[u] ;
			}
		}
		return flow ;
	}
} ;

netWork net ;

int read () {
	char c = ' ' ;
	int x = 0 ;
	while ( c < '0' || c > '9' )
		c = getchar () ;
	while ( c >= '0' && c <= '9' ) {
		x = x * 10 + c - '0' ;
		c = getchar () ;
	}
	return x ;
}

void work () {
	int n , m ;
	int d , u , v , c ;
	net.init () ;
	n = read () , m = read () ;
	net.s = 0 , net.t = n - 1 , net.nv = net.t + 1 ;
	while ( m -- ) {
		u = read () , v = read () , c = read () , d = read () ;
		LL cc = c * 1000000LL + 1 ;
		if ( d )
			net.addedge ( u , v , cc , cc ) ;
		else
			net.addedge ( u , v , cc ) ;
	}
	LL flow = net.ISAP () ;
	printf ( "%I64d\n" ,  flow % 1000000 ) ;
}

int main () {
	int T , cas = 0 ;
	scanf ( "%d" , &T ) ;
	while ( T -- ) {
		printf ( "Case %d: " , ++ cas ) ;
		work () ;
	}
	return 0 ;
}