Description

There is an undirected graph with $N$ vertices and $M$ edges, and each edge has a weight. The graph has no multiple edges and no self-loops. The vertices are numbered starting from $0$.

Exactly $N - 1$ edges have weight $1$. All other edges have weight $\ge \left\lceil \frac{N}{3} \right\rceil$ and $\le N$. Also, if we only consider the edges with weight $1$, the whole graph forms a tree.

Now you need to traverse every vertex exactly once, while making the total weight of the edges you travel as small as possible.

Find the minimum possible total edge weight.

Reminder:

• You may go back and forth along an edge.
• You may choose any vertex to start from.
• You have only one person.

Input Format

The first line contains two integers $N, M$.

The next $M$ lines each contain three integers $x_i, y_i, w_i$, indicating that there is an edge between $x_i$ and $y_i$ with weight $w_i$.

Output Format

Output the minimum total edge weight required to traverse every vertex exactly once.

9 10
0 1 1
0 2 1
0 3 1
1 4 1
2 5 1
2 6 1
3 7 1
3 8 1
2 4 5
6 7 3

11

Hint

Sample Explanation

An optimal path is $4\to 1\to 0\to 2\to 5\to 2\to 6\to 7\to 3\to 8$, with total edge weight $1+1+1+1+1+1+3+1+1=11$.

Subtasks

This problem uses bundled testdata.

• Subtask 1 ($4$ points): $N\le 6$, $M\le 10$.
• Subtask 2 ($8$ points): $N\le 20$, $M\le 40$.
• Subtask 3 ($8$ points): $N\le 5\times 10^3$, $M\le 10^5$, and $w_i=1$ or $\left\lceil\frac{N}{2}\right\rceil\le w_i\le N$.
• Subtask 4 ($24$ points): $N\le 100$, $M\le 200$.
• Subtask 5 ($8$ points): $N\le 500$, $M\le 10^3$.
• Subtask 6 ($12$ points): $N\le 5\times 10^3$, $M\le 10^4$.
• Subtask 7 ($20$ points): $N\le 8\times 10^4$, $M\le 1.6\times 10^5$.
• Subtask 8 ($16$ points): No special restrictions.

For $100\%$ of the data, it is guaranteed that $4\le N\le 5\times 10^5$, $N-1 \le M\le 2\times 10^6$, $0\le x_i,y_i\le N-1$, and $w_i=1$ or $\left\lceil \frac{N}{3}\right\rceil\le w_i\le N$.

Notes

This problem is translated from Canadian Computing Olympiad 2020 Day 1 T3 Mountains and Valleys。

Translated by ChatGPT 5