Jumbled Trees

Description:

Input:

The first line contains three integers $$$n$$$, $$$m$$$, and $$$p$$$ — the number of vertices, the number of edges, and the prime modulus ($$$1 \le n \le 500$$$; $$$1 \le m \le 1000$$$; $$$2 \le p \le 10^9$$$, $$$p$$$ is prime).

Next $$$m$$$ lines contain three integers $$$u_i$$$, $$$v_i$$$, $$$x_i$$$ each — the two endpoints of the $$$i$$$-th edge and the target value of that edge's counter ($$$1 \le u_i, v_i \le n$$$; $$$0 \le x_i < p$$$; $$$u_i \neq v_i$$$).

The graph is connected. There are no loops, but there may be multiple edges between the same two vertices.

Output:

If the target values on counters cannot be achieved, print -1.

Otherwise, print $$$t$$$ — the number of operations, followed by $$$t$$$ lines, describing the sequence of operations. Each line starts with integer $$$v$$$ ($$$0 \le v < p$$$) — the counter increment for this operation. Then, in the same line, followed by $$$n - 1$$$ integers $$$e_1$$$, $$$e_2$$$, ... $$$e_{n - 1}$$$ ($$$1 \le e_i \le m$$$) — the edges of the spanning tree.

The number of operations $$$t$$$ should not exceed $$$2m$$$. You don't need to minimize $$$t$$$. Any correct answer within the $$$2m$$$ bound is accepted. You are allowed to repeat spanning trees.

Sample Input:

3 3 101
1 2 30
2 3 40
3 1 50

Sample Output:

3
10 1 2
20 1 3
30 2 3

Sample Input:

2 2 37
1 2 8
1 2 15

Sample Output:

2
8 1
15 2

Sample Input:

5 4 5
1 3 1
2 3 2
2 5 3
4 1 4

Sample Output:

-1