Mountains and Valleys

You are planning a long hiking trip through interesting but well-known terrain. There are $N$ sites you want to visit and $M$ trails connecting pairs of sites. Each trail has a positive integer difficulty level.

The trail system is special. Exactly $N-1$ trails have difficulty level 1, and these are completely flat. Every other trail has difficulty at least $\lceil N/3 \rceil$, and these are very mountainous. ($\lceil x \rceil$ is the smallest integer greater than or equal to $x$.)

It is possible to travel between any two sites using only the trails with difficulty level 1.

You want to visit every site at least once. You may start at any site, and you must end at a different site. Find the walk with the minimum total difficulty. Walking a trail with difficulty $d$ a total of $k$ times adds $k \cdot d$ to the sum.

The first line contains two space-separated integers $N$ ($4 \le N \le 500000$) and $M$ ($N-1 \le M \le 2000000$). Each of the next $M$ lines contains three space-separated integers $x_i$, $y_i$, and $w_i$, meaning a trail joins sites $x_i$ and $y_i$ with difficulty $w_i$ ($1 \le i \le M$; $0 \le x_i, y_i \le N-1$; $x_i \ne y_i$). Each pair of sites is joined by at most one trail. Each $w_i$ is either 1 or satisfies $\lceil N/3 \rceil \le w_i \le N$.

Output one integer: the minimum sum of difficulty levels over all walks that visit every site at least once.

The first figure shows the trails with difficulty level 1.

The second figure shows all trails with their difficulty levels.

The third figure shows all trails except those with difficulty level 1.

An optimal walk is 4 → 1 → 0 → 2 → 5 → 2 → 6 → 7 → 3 → 8, with total cost 1 + 1 + 1 + 1 + 1 + 1 + 3 + 1 + 1 = 11. No walk that visits every site has a lower total difficulty.