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

请判断是否能使每条边的计数器值模素数 $p$ 后等于其目标值 $x_i$，如果可以，请给出实现该目标的操作序列。

输入格式

第一行包含三个整数 $n, m, p$ —— 顶点数、边数和素数模数（$1 \le n \le 500$；$1 \le m \le 1000$；$2 \le p \le 10^9$，$p$ 为素数）。

接下来 $m$ 行，每行包含三个整数 $u_i, v_i, x_i$ —— 第 $i$ 条边的两个端点以及该边计数器的目标值（$1 \le u_i, v_i \le n$；$0 \le x_i < p$；$u_i \neq v_i$）。

图是连通的。图中没有自环，但两个顶点之间可能存在多条边。

输出格式

如果无法达到计数器的目标值，输出 -1。

否则，输出 $t$ —— 操作次数，随后输出 $t$ 行，描述操作序列。每行以整数 $v$（$0 \le v < p$）开头，表示该次操作的增量。随后在同一行中，输出 $n - 1$ 个整数 $e_1, e_2, \dots, e_{n-1}$（$1 \le e_i \le m$），表示生成树包含的边。

操作次数 $t$ 不应超过 $2m$。你不需要最小化 $t$。任何在 $2m$ 限制内的正确答案均可被接受。允许重复使用相同的生成树。

样例

样例输入 1

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

样例输出 1

3
10 1 2
20 1 3
30 2 3

样例输入 2

2 2 37
1 2 8
1 2 15

样例输出 2

2
8 1
15 2

样例输入 3

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

样例输出 3

-1