Jumbled Trees

Input

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

The following $m$ lines each contain three integers u_i, v_i, x_i~(1 \le u_i, v_i \le n, 0 \le x_i < p, u_i \ne v_i) — the endpoints of the $i$-th edge and its target value.

The graph is connected. It contains no self-loops, but there may be multiple edges between the same pair of vertices.

Output

If it is impossible to reach the target values, print $-1$.

Otherwise, print the number of operations $t$, followed by $t$ lines describing them. Each line starts with an integer v~(0 \le v < p) — the increment value for this operation. Then follow n - 1 integers e_1, e_2, \dots, e_{n-1}~(1 \le e_i \le m) — the edges that form the chosen spanning tree.

The number of operations $t$ must not exceed $2m$. You do not need to minimize $t$: any valid solution within this bound will be accepted. It is allowed to use the same spanning tree multiple times.

Examples