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 xi 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 ≤ n ≤ 500, 1 ≤ m ≤ 1000, 2 ≤ p ≤ 109, p is prime).

Next m lines contain three integers ui, vi, xi each - the two endpoints of the i-th edge and the target value of that edge’s counter (1 ≤ ui, vi ≤ n, 0 ≤ xi < p, ui ≠ vi).

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 ≤ v < p) - the counter increment for this operation. Then, in the same line, followed by n - 1 integers e1, e2, ..., en-1 (1 ≤ ei ≤ 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.