背景

给定一个无向连通图，包含$n$个顶点和$m$条边。每条边有一个关联的计数器，初始值为$0$。在一次操作中，你可以选择一个生成树，并将任意值$v$加到该生成树中所有边的计数器上。

判断是否可以使每条边的计数器值等于其目标值$x_i$（对质数$p$取模后的值），并提供一系列操作来实现该目标。

描述

输入

第一行包含三个整数$n$，$m$和$p$，分别表示顶点数、边数和质数模数$(1 \leq n \leq 500; 1 \leq m \leq 1000; 2 \leq p \leq 10^9, p$为质数)。

接下来的$m$行，每行包含三个整数$u_i$，$v_i$和$x_i$，表示第$i$条边的两个端点及其目标计数器值$(1 \leq u_i, v_i \leq n; 0 \leq x_i < p; u_i \neq v_i)$。

图是连通的。没有自环，但可能有多重边。

输出

如果无法实现目标计数器值，输出$-1$。

否则，输出一个整数$t$，表示操作的数量，接下来输出$t$行描述操作的序列。

每行从一个整数$v$开始，表示本次操作的计数器增量$(0 \leq v < p)$，然后是$n-1$个整数$e_1, e_2, \dots, e_{n-1}$，表示生成树的边编号$(1 \leq e_i \leq m)$。

操作数$t$不超过$2m$。无需最小化$t$。在$2m$范围内的任意正确答案都被接受，可以重复使用生成树。

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

3
10 1 2
20 1 3
30 2 3

2 2 37
1 2 8
1 2 15

2
8 1
15 2

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

-1