410670: GYM104072 H Minimize

Johnny found a set of points in the euclidean plane and noticed that each of the points has a certain weight $$$w_i$$$ associated with it. Johnny likes to optimize absolutely everything! This is why today he is trying to minimize anything he possibly can.

He started thinking about connecting those points with straight lines in order to form a tree that covers the entire set such that the total sum of the lengths of the segments connecting the points is the smallest possible. On this tree, node $$$i$$$ corresponds to point $$$i$$$. Then, he came up with a strange cost function that is computed in the following way:

• He first roots the tree at node $$$1$$$.
• If $$$node$$$ is a leaf, then $$$c_{node}\ =\ w_{node}$$$.
• Otherwise, let $$$x_1$$$, $$$x_2$$$, .. $$$x_k$$$ be the children of $$$node$$$. He first minimizes $$$c_{x_1}$$$, $$$c_{x_2}$$$, .. $$$c_{x_k}$$$. Then, for some ordering of the children $$$y_1$$$, $$$y_2$$$ .. $$$y_k$$$ that is a permutation of the set $$$\{1,\ 2\ ..\ k\}$$$ $$$c_{node}\ = w_{node}\ + \ c_{x_{y_1}} + \ {c_{x_{y_2}}}^2 + .. + {c_{x_{y_k}}}^k$$$. Among all such orderings, Johnny picks the one that minimizes $$$c_{node}$$$.

Johnny quickly realized that this cost functions grows very quickly and he wouldn't be able to compute it. He then remembered from his competitive programming course that when the answer to a problem is too big to be computed, he usually computed it modulo some number $$$MOD$$$. This is exactly what Johnny did! He additionally picks a new number $$$MOD$$$ and will do all calculations modulo $$$MOD$$$.

Despite having a good idea, Johnny makes a crucial mistake: instead of calculating the residue of the cost function modulo $$$MOD$$$, he instead calculates the minimum possible residue modulo $$$MOD$$$, for each of the $$$c_i$$$.

Compute a program to find the answer produced by Johnny's algorithm. Given a set of points and a number $$$MOD$$$, you are asked to do the following:

1. Find a spanning tree with the sum of lengths of edges being the smallest possible. The length of an edge is the euclidean distance between the two points it connects. If there are multiple such trees, you may pick any.
2. Compute the cost function modulo $$$MOD$$$, having rooted the tree in node $$$1$$$. Note that at each point of computing $$$c_i$$$, you should minimize the residue modulo $$$MOD$$$ instead of the actual cost function itself.

The first line of the input contains two integers: $$$N$$$ $$$(1 \le N \le 5000)$$$ and $$$MOD$$$ $$$(1 \le MOD \le 2*10^9)$$$. The next $$$N$$$ lines each contain three integers: $$$x_i$$$, $$$y_i$$$, $$$w_i$$$ $$$(-10^9 \le x_i, y_i \le 10^9\ and\ 0 \le w_i \le 10^9)$$$, coordinates and weight of point $$$i$$$. It is guaranteed that no two points share the same coordinates.

The first $$$N-1$$$ lines of the output should contain two integers $$$u$$$ and $$$v$$$, representing the edges of the tree you picked. This tree must have the total sum of lengths of its edges the minimum among all possible trees covering the entire set of points. If there are multiple such trees, you may pick any of them. The next line must contain $$$N$$$ integers $$$c_i$$$, where $$$c_i$$$ is the cost function computed for node $$$i$$$ in the tree that you previously picked.

3 10
0 0 2
-1 -1 3
1 1 2

1 2
1 3
3 3 2 

5 19
-2 -2 1
-3 -2 16
5 0 14
1 -4 18
-5 3 17

2 5
1 2
4 3
1 4
1 14 14 13 17