题目描述

给定一个无向图，其中两个顶点之间可以有多条边连接，求该图的最小割的大小。即至少需要移除多少条边才能将图分成两个子图？

输入

输入包含多个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $M$（$2 \leq N \leq 500$，$0 \leq M \leq N \times (N - 1) / 2$），其中 $N$ 是顶点数。接下来的 $M$ 行，每行包含三个整数 $A$、$B$ 和 $C$（$0 \leq A, B < N$，$A \neq B$，$C > 0$），表示有 $C$ 条边连接顶点 $A$ 和 $B$。

输出

每个测试用例仅输出一行，包含该图的最小割的大小。如果图已经不连通，则输出 $0$。

输入样例

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

输出样例

2
1
2

题目来源

Baidu Star 2006 Semifinal
Wang, Ying (Originator)
Chen, Shixi (Test cases)