408057: GYM102968 G Complete Journey

You will make a trip in the mountains! There are $$$N$$$ peaks (numbered from $$$1$$$ to $$$N$$$) you want to visit and $$$M$$$ undirected trails connecting these peaks; each trail has a distinct value of beauty. It is guaranteed that you can reach any peak from any other peak using the trails.

The value of beauty of a path between two peaks is the maximum value across all the trails that form this path.

In a journey between two peaks you will take a path between them with minimum value of beauty, because the other ones are considered to be too dangerous. So, the value of beauty of a journey between two peaks is the minimum value of beauty of a path among all the paths between these two peaks.

In your trip you want to make a complete journey. You want to visit all the peaks in a fixed order by making multiple journeys, so that the sum of values of beauty of all the journeys is as much as possible.

In other words, you need to find a permutation of the peaks $$$\{p_1, p_2, ..., p_N\}$$$, so that the sum of values of beauty of the journeys $$$(p_1, p_2)$$$, $$$(p_2, p_3)$$$, ..., $$$(p_{N-1}, p_N)$$$ is the maximum among all the permutations.

The first line of the input contains $$$2$$$ integers: $$$1 \leq N \leq 10^5$$$, the number of peaks; $$$1 \leq M \leq 2*10^5$$$, the number of trails.

Each of the following $$$M$$$ lines contains $$$3$$$ integers: $$$x_i, y_i, c_i$$$, representing a bi-directional trail between the peaks $$$x_i$$$ and $$$y_i$$$ having the value of beauty $$$c_i$$$, $$$1 \leq x_i, y_i \leq N$$$, $$$1 \leq c_i \leq 10^9$$$. All values of beauty are distinct.

The first line of the output will contain $$$CMax$$$, the maximum total value of beauty of a permutation.

The second line will contain a valid permutation of length $$$N$$$, having the total value of beauty $$$CMax$$$.

3 2
1 2 1
1 3 2

4
1 3 2

10 17
2 10 1
10 3 2
10 6 3
2 1 4
2 3 5
3 5 6
1 4 7
4 5 8
5 6 9
4 8 10
1 10 11
8 7 12
1 9 13
9 3 14
6 7 15
4 9 16
9 5 17

90
2 9 5 6 4 3 8 1 7 10

In the first example, the value of beauty of the journey $$$(1, 3)$$$ is $$$2$$$, and the value of beauty of the journey $$$(3, 2)$$$ is $$$2$$$, hence the sum is 4. This is the maximum possible sum.