Second best minimum spanning tree - MarisaOJ: Marisa Online Judge

Second best minimum spanning tree

Time limit: 1000 ms
Memory limit: 256 MB
Given an undirected graph with $n$ vertices and $m$ edges. Find the sum of weights of edges in the second smallest spanning tree of the graph. Note that it must be strictly more than the weight of the minimum spanning tree. ### Input - The first line contains two integers $n$ and $m$. - The next $m$ lines each contain three integers $u, v, w$, indicating an edge between $u$ and $v$ with weight $w$. ### Output - Print an integer, the weight of the second smallest spanning tree. ### Constraints - $1 \le n,m \le 300000$. - $1 \le u,v \le n$. - $1 \le w \le 10^9$. ### Example Input: ``` 4 4 1 2 1 2 3 2 2 4 2 3 4 3 ``` Output: ``` 6 ```