E Stands for Efficiency

June Square is a young financial company whose goal is to develop a new, efficient, decentralized payment system written entirely in their favourite programming language JavaScri... OCaml! Obviously, the name of their currency would have to be JScoin.

The work started in 2015 when June Square invested in building $N$ geographically distributed cryptocurrency storage units with communication lines between them. Since this system is global, each person in the world gets a wallet created in one of these storage units. To transfer a single JScoin between two people, the system finds the shortest path in the communications graph between the storage units holding their respective wallets and transfers JScoin along that path. Moving a single JScoin between two directly connected storage units takes exactly 1 megawatt, thus, transferring a JScoin along a path traversing $L$ connections takes exactly $L$ megawatts.

To optimise the energy budget, storage units should be built in distant areas with cheap energy. As a result, creating direct connections between them becomes very complicated and expensive. Therefore, the June Square leadership decided to limit the number of direct connections to each storage unit by $R$.

Such limitations mean that the connections had to be designed thoroughly. The analytics department has already predicted the number of JScoins transferred during a year between each pair of storage units. Given that knowledge, design the connections network between the units so that the total predicted energy expenditure over a year will be as small as possible.

Input Data

You are given a zip-archive with $12$ tests: 01, 02, $\ldots$, 12.

Download inputs (problem-e-inputs.zip)

The first line of each test contains three integers: the number of storage units $N$ ($2 \le N \le 10^4$), the number of JScoin transaction predictions $M$ ($1 \le M \le 10^6$), and the maximum number of direct connections per unit $R$ ($2 \le R \le 4$).

$M$ lines follow. The $i$-th of these lines contains three integers $s_i$, $d_i$, $q_i$ ($1 \le s_i, d_i \le N$, $1 \le q_i \le 10^5$, $s_i \neq d_i$): two storage unit indices and the predicted number of JScoins to transfer between them. No pair of storage units is listed more than once.

Here is a short description of these tests:

Output Data

You should submit files 01.out, 02.out, $\ldots$, 12.out with answers to corresponding inputs. Some of the files may be missing.

Each of these files should be in the following format:

• The first line should contain the number of direct connections $K$.
• The next $K$ lines should contain the connections as the indices of connected storage units, separated by whitespace.

Scoring

If any of the following happens in your output:

• there is a format error;
• there is a storage unit connected to itself;
• two storage units are connected more than once;
• a storage unit has more than $R$ connections;
• there is no possibility to pass all required JScoins through the connection graph;

then your output is considered to be incorrect.

Otherwise, let $D_{i,j}$ be the shortest distance from unit $i$ to unit $j$ using the provided connections. The total amount of energy in megawatts (or points) is then computed as follows: $$\sum_{i=1}^{M} D_{s_i,d_i} \cdot q_i.$$

Your final score for the test is calculated as follows:

• If the output is incorrect, it gets $0$ points.
• Otherwise, it will be proportional to the cube of the lowest amount of points among all participants for this test divided by the number of points for your output: $300 \cdot \left( \frac{\texttt{best\_points}}{\texttt{your\_points}} \right)^3$.

Note that the scoreboard will show your best score for each test among all your submissions.

Problem by Jane Street