Background

In the vast universe...

Problem Description

There is a group of creatures called ccj who discovered a supercluster. There are $n$ stars and $m$ bidirectional interstellar routes, and traveling along the $i$-th route consumes a fuel cost of $val_i$. Two stars are not in the same galaxy if and only if there is no route between them, and there is no path that can reach one from the other. Only stars can refuel spaceships. Each trip uses a simple path. Because the fuel system is too crude, each fuel tank can only be used for one trip. Their leader ccj wants to build a base on one of the stars. However, ccj spent too much money on high-speed ships and does not have much money to buy fuel tanks, so for any trip between two stars he will always choose the most economical way, buying the smallest possible fuel tank. He wants to ask you: how much total fuel should be prepared for the base, so that no matter which star the base is built on, it can reach all other stars in the same galaxy from that base.

However, the supercluster has gone to war, and some black holes changed the spatial structure here. The creatures only know the fuel cost of each route, but cannot find which two stars it connects. Their scientists discovered a property: each war has a marker value $q$. The routes can be arranged in different orders, and for one such arrangement, the $i$-th route connects star $((q^{i} \bmod 2^{32}+i \times val_i) \bmod n+n) \bmod n+1$ and star $((q^{i} \bmod 2^{32}-i \times val_i) \bmod n+n) \bmod n+1$. All operations are performed as unsigned integer operations. If the two connected stars are the same, it means the scientists made a mistake, and this route should be ignored. ccj’s goal changed. He wants to know: over all possible galaxy structures, what is the minimum total fuel that must be prepared, so that in such a structure, no matter which star the base is built on, it can reach all other stars in the same galaxy (the connected component of that star) under that structure.

You need to output the route arrangement order.

Input Format

The first line contains three positive integers $n$, $m$, and $q$, meaning there are $n$ stars, $m$ routes, and the war marker value $q$.

The second line contains $m$ positive integers $val_i$, where $val_i$ is the fuel cost of the $i$-th route.

Output Format

The first line contains one positive integer $ans$, which is the value ccj asks you to compute.

From the second line to the $(m+1)$-th line, output one integer per line. On the $i$-th line, output $val_{i-1}$ under this arrangement.

3 5 2
1 2 3 4 5

1
5
4
2
3
1

Hint

Sample Explanation:

These $5$ routes are:

Round trip between $2$ and $2$, fuel cost $5$.

Round trip between $1$ and $1$, fuel cost $4$.

Round trip between $3$ and $3$, fuel cost $2$.

Round trip between $2$ and $2$, fuel cost $3$.

Round trip between $1$ and $2$, fuel cost $1$.

The first four routes are ignored, so there are four galaxies: $\{1,2\},\{3\},\{4\},\{5\}$.

When the base is built on $1$, traveling from $1$ to $2$ requires buying a fuel tank of size $1$. It can be seen that there is no better answer than this.

Constraints: $2 \le n \le 100\quad 1 \le m \le 40\quad 0 \le q \le 10^9\quad 0 \le val_i \le 1000$.

Your answer only needs to be better than the std, or equal to the std and the construction is correct.

For testdata $1 \sim 4$, the optimal answer is required; for testdata $5 \sim 10$, a suboptimal answer is accepted.

This problem will provide the input of testdata 10
Input Data

For detailed ranges, see “standard solution”.

All testdata are randomly generated. Please pay attention to constants.

Translated by ChatGPT 5