Minimum Cut of an Undirected Graph

Given an undirected weighted graph \(G\), the minimum cut of \(G\) is defined as the minimum total weight of an edge set whose removal separates \(G\) into two connected components. In other words, find a partition of the vertices into two nonempty sets such that the sum of weights of the edges crossing the partition is minimized.

You are given a graph \(G\) with \(n\) vertices and \(m\) edges. Each edge is described by two endpoints and its weight. Your task is to compute the minimum cut value of \(G\).

The problem can be solved by implementing the Stoer-Wagner algorithm which runs in \(O(n^2)\) time in its simplest form.

inputFormat

The first line contains two integers \(n\) and \(m\) where \(n\) is the number of vertices and \(m\) is the number of edges.

Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\), representing an undirected edge between vertices \(u\) and \(v\) with weight \(w\). The vertices are numbered from 1 to \(n\). It is guaranteed that \(n \ge 2\) and \(m \ge 1\).

outputFormat

Output a single integer representing the minimum cut value of the given graph.

sample

2 1
1 2 10

10