Description

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)<\sum_{e \in E_S}value(e)$.

Xiao C was stumped and came to you for help to solve this problem.

Input Format

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 Format

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

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

11

Hint

• 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