题目描述

定义无向图 $G$ 的最小割为：一个去掉后可以使 $G$ 变成两个连通分量，且边权和最小的边集的边权和。

给出一张无向图 $G$，求其最小割。

输入格式

第一行，两个数 $n,m$，表示点数与边数。

接下来 $m$ 行，每行三个正整数 $a_i,b_i,w_i$，表示 $a_i$ 到 $b_i$ 有一条边权为 $w_i$ 的边。

输出格式

一行，一个整数表示 $G$ 的最小割，如果图不联通，请输出 0 。

4 6
1 2 5
1 3 1
2 4 1
3 4 2
2 3 1
1 4 2

4

提示

对于前 $20\%$ 的数据， $n\leq 10$。
对于前 $40\%$ 的数据， $n\leq 100$。
对于另外 $10\%$ 的数据，保证输入为一棵树。
对于另外 $10\%$ 的数据，保证输入为一条链。
对于 $100\%$ 的数据， $n\leq 600,m\leq \frac{n\times (n-1)}{2}$ ，保证 $\sum_{i=1}^{m}w_i \leq10^9$ 。

PS：想交 最大流/最小割树 的就省省吧。