Description

Original source: BeiJing 2010 Team Competition

Given an undirected graph with $N$ vertices and $M$ edges, find the strictly second-minimum spanning tree.

Let the sum of edge weights in the minimum spanning tree be $\text{sum}$. The strictly second-minimum spanning tree is the one with the smallest edge weight sum among all spanning trees whose edge weight sums are greater than $\text{sum}$.

Input Format

The first line contains two integers $N$ and $M$, representing the number of vertices and edges in the undirected graph, respectively.

The next $M$ lines each contain three integers $x$, $y$, and $z$, indicating an edge between vertex $x$ and vertex $y$ with a weight of $z$.

Output Format

Output a single line containing only one number, which is the edge weight sum of the strictly second-minimum spanning tree.

It is guaranteed that the strictly second-minimum spanning tree exists.

Sample 1

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

11

Data Range and Hints

For all data, $1\le N\le 10^5$, $1\le M\le 3\times 10^5$. The undirected graph contains no self-loops, and edge weights are non-negative and do not exceed $10^9$.