Description

Define the minimum cut of an undirected graph $G$ as follows: it is a set of edges such that removing these edges can make $G$ split into two connected components, and the sum of edge weights in this set is minimal.

Given an undirected graph $G$, find its minimum cut.

Input Format

The first line contains two numbers $n, m$, representing the number of vertices and the number of edges.

The next $m$ lines each contain three positive integers $a_i, b_i, w_i$, indicating that there is an edge between $a_i$ and $b_i$ with weight $w_i$.

Output Format

Output one line with one integer representing the minimum cut of $G$. If the graph is disconnected, output 0.

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

4

Hint

For the first $20\%$ of the testdata, $n \leq 10$.
For the first $40\%$ of the testdata, $n \leq 100$.
For another $10\%$ of the testdata, the input is guaranteed to be a tree.
For another $10\%$ of the testdata, the input is guaranteed to be a chain.
For $100\%$ of the testdata, $n \leq 600, m \leq \frac{n\times (n-1)}{2}$, and it is guaranteed that $\sum_{i=1}^{m} w_i \leq 10^9$.

PS: If you want to submit “maximum flow / minimum cut tree”, just forget it.

Translated by ChatGPT 5