Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2753
Min Cut (Destroy Trade Net)

Time Limit: 15 Seconds      Memory Limit: 32768 KB

Given an undirected graph, in which two vertexes can be connected by multiple edges, what is the min-cut of the graph? i.e. how many edges must be removed at least to partition the graph into two disconnected sub-graphes?

Input

Input contains multiple test cases. Each test case starts with two integers N and M (2<=N<=500, 0<=M<=N*(N-1)/2) in one line, where N is the number of vertexes. Following are M lines, each line contains M integers A, B and C (0<=A,B<N, A<>B, C>0), meaning that there C edges connecting vertexes A and B.

Output

There is only one line for each test case, which is the min-cut of the graph. If the graph is disconnected, print 0.

Sample Input

3 3
0 1 1
1 2 1
2 0 1
4 3
0 1 1
1 2 1
2 3 1
8 14
0 1 1
0 2 1
0 3 1
1 2 1
1 3 1
2 3 1
4 5 1
4 6 1
4 7 1
5 6 1
5 7 1
6 7 1
4 0 1
7 3 1

Sample Output

2
1
2

Author: WANG, Ying
Source: Baidu Star 2006 Semi-Final
Submit    Status