Strictly Second Minimum Spanning Tree

Given an undirected weighted graph, your task is to compute its strictly second minimum spanning tree. Let \(E_M\) be the edge set chosen by the minimum spanning tree (MST) and \(E_S\) be the edge set chosen by the strictly second minimum spanning tree. They must satisfy:

\[ \sum_{e \in E_M} value(e) < \sum_{e \in E_S} value(e) \]

If there exists a spanning tree with a total weight strictly greater than the MST and is the smallest possible value among all such spanning trees, output its total weight. Otherwise, output -1.

The graph is given with n nodes and m edges. There may be multiple valid spanning trees. Use an efficient algorithm such as MST computation with binary lifting to determine the candidate replacements.

inputFormat

The first line contains two integers n and m (number of nodes and edges respectively).

Each of the following m lines contains three integers: u v w, representing an undirected edge connecting nodes u and v with weight w.

outputFormat

Output a single line containing the total weight of the strictly second minimum spanning tree. If such a spanning tree does not exist, output -1.

sample

3 3
1 2 1
2 3 2
1 3 3

4