P4180 [BJWC2010] Strictly Second Minimum Spanning Tree

Xiao C recently learned many algorithms for the minimum spanning tree, such as Prim, Kruskal, and cycle-canceling, etc. Just as Xiao C was feeling proud, Xiao P poured cold water on him. Xiao P asked Xiao C to find the second minimum spanning tree of an undirected graph, and it must be strictly second, that is: if the edge set chosen by the minimum spanning tree is $E_M$, and the edge set chosen by the strictly second minimum spanning tree is $E_S$, then it must satisfy: (here $value(e)$ denotes the weight of edge $e$) $\sum_{e \in E_M}value(e)

The first line contains two integers $N$ and $M$, denoting the number of vertices and edges of the undirected graph. The next $M$ lines each contain three numbers $x, y, z$, indicating that there is an edge between vertex $x$ and vertex $y$ with weight $z$.

Output one line with a single number, the sum of edge weights of the strictly second minimum spanning tree.

- The undirected graph may contain self-loops. Constraints: - For 50% of the testdata, $N \le 2000$, $M \le 3000$. - For 80% of the testdata, $N \le 5 \times 10^4$, $M \le 10^5$. - For 100% of the testdata, $N \le 10^5$, $M \le 3 \times 10^5$, edge weights $\in [0,10^9]$, and the testdata guarantees that a strictly second minimum spanning tree exists. Translated by ChatGPT 5