Задан неориентированный связный граф с n вершинами и m ребрами. Каждое ребро имеет счетчик, изначально равный 0. За одну операцию Вы можете выбрать произвольное остовное дерево и добавить любое значение v ко всем ребрам этого остовного дерева.

Определите, можно ли сделать каждый счетчик равным его целевому значению xi по простому модулю p, и предоставьте последовательность операций, обеспечивающих это.

Входные данные

Первая строка содержит три целых числа n, m и p - количество вершин, количество ребер и простой модуль (1 ≤ n ≤ 500, 1 ≤ m ≤ 1000, 2 ≤ p ≤ 109, p - простое число).

Следующие m строк содержат по три целых числа ui, vi, xi - две конечные точки i-го ребра и целевое значение счетчика этого ребра (1 ≤ ui, vi ≤ n, 0 ≤ xi < p, ui ≠ vi).

Граф связный. Циклов нет, но между одними и теми же двумя вершинами может быть несколько ребер.

Выходные данные

Если целевые значения счетчиков не могут быть достигнуты, выведите -1.

В противном случае выведите t - количество операций, а затем t строк, описывающих последовательность операций. Каждая строка начинается с целого числа v (0 ≤ v < p) - приращения счетчика для этой операции. Затем в той же строке следуют n - 1 целых чисел e1, e2, ..., en-1 (1 ≤ ei ≤ m) - ребра остовного дерева.

Количество операций t не должно превышать 2m. Вам не нужно минимизировать t. Принимается любой правильный ответ в пределах 2m. Вам разрешено повторять остовные деревья.