Canadian Computing Olympiad: 2020 Day 1, Problem 3

You are planning a long hiking trip through some interesting, but well-known terrain. There are ~N~ interesting sites you would like to visit and ~M~ trails connecting pairs of sites. Each trail has a difficulty level indicated as a positive integer.

The trail system is a bit special, however. There are exactly ~N-1~ trails with difficulty level 1 (these are completely flat trails), and the rest of the trails all have a difficulty level of at least ~\left\lceil \frac N 3 \right\rceil~ (these are very mountainous trails). (The ceiling of ~x~, denoted as ~\left\lceil x \right\rceil~, is the smallest integer greater than or equal to ~x~.)

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

You would like to visit every site, starting your walk from any site of your choice and finishing at some other site, such that you visit each site at least once and the total sum of difficulty levels is minimum among all walks. Note that walking a trail ~k~ times with difficulty level ~d~ contributes a value of ~k \cdot d~ to the sum of difficulty levels.

Input Specification

The first line of input contains two space-separated integers ~N~ ~(4 \le N \le 500\,000)~ and ~M~ ~(N-1 \le M \le 2\,000\,000)~.

The next ~M~ lines contain three space-separated integers ~x_i~, ~y_i~, and ~w_i~, describing the trail between sites ~x_i~ and ~y_i~ with difficulty level ~w_i~ ~(1 \le i \le M; 0 \le x_i, y_i \le N-1; x_i \ne y_i)~. Note that there is at most one trail between every pair of sites, and that ~w_i=1~ or ~\left\lceil \frac N 3 \right\rceil \le w_i \le N~.

For 1 of the 25 marks available, ~N \le 6~ and ~M \le 10~.

For an additional 2 of the 25 marks available, ~N \le 20~ and ~M \le 40~.

For an additional 2 of the 25 marks available, ~N \le 5\,000~, ~M \le 10\,000~, and either ~w_i=1~ or ~\left\lceil \frac N 2 \right\rceil \le w_i \le N~.

For an additional 6 of the 25 marks available, ~N \le 100~ and ~M \le 200~.

For an additional 2 of the 25 marks available, ~N \le 500~ and ~M \le 1\,000~.

For an additional 3 of the 25 marks available, ~N \le 5\,000~ and ~M \le 10\,000~.

For an additional 5 of the 25 marks available, ~N \le 80\,000~ and ~M \le 160\,000~.

Output Specification

Output one integer, which is the minimum sum of difficulty levels taken for all trails walked to visit each site once.

Sample Input

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

Sample Output

11

Explanation of Output for Sample Input

This is the set of flat trails.

This is the entire set of trails with all the difficulty levels.

This is the entire set of trails, with trails with difficulty level 1 being omitted.

An optimal walk for this set of trails is ~4 \to 1 \to 0 \to 2 \to 5 \to 2 \to 6 \to 7 \to 3 \to 8~ with a total cost of ~1+1+1+1+1+1+3+1+1=11~. There is no way to make a walk that visits all the sites at least once with a lower total difficulty level cost.