Second Smallest Spanning Tree

Time limit2sMemory limit128 MB

Summary
Find the minimum spanning tree, then compute the smallest spanning tree whose weight is strictly greater than the MST weight, or report -1 if none exists.
Level

Hard8 of 10

Topics
Minimum spanning tree, Tree, Graph, Union-find
Solved
No attempts yet

Problem

Given an undirected graph G, find the weight of a spanning tree whose total weight is greater than the minimum spanning tree and is as small as possible among such trees. This tree is called the second smallest spanning tree.

The figure shows an example of a minimum spanning tree and a second smallest spanning tree.

Input

The first line contains the number of vertices V (1 <= V <= 50,000) and the number of edges E (1 <= E <= 200,000). Each of the next E lines contains two vertices joined by an edge and the weight of that edge. Each weight is an integer from 0 to 100,000. The answer does not exceed (2^{31}-1).

Vertices are numbered from 1 to V.

Output

Print the total weight of the second smallest spanning tree. If no spanning tree exists, or if no spanning tree has total weight strictly greater than the minimum spanning tree, print -1.

Examples1

  1. Example 1

    Input
    7 12
1 2 8
1 3 5
2 3 10
2 4 2
2 5 18
3 4 3
3 6 16
4 5 12
4 6 30
4 7 14
5 7 4
6 7 26
    Expected output
    44