You are given an undirected connected graph with $$$n$$$ vertices and $$$m$$$ edges. Each edge has an associated counter, initially equal to $$$0$$$. In one operation, you can choose an arbitrary spanning tree and add any value $$$v$$$ to all edges of this spanning tree.

Determine if it's possible to make every counter equal to its target value $$$x_i$$$ modulo prime $$$p$$$, and provide a sequence of operations that achieves it.

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 \lt 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 \lt 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.

Jumbled Trees

Examples