e-olymp
Задачи

Экскалибур

Экскалибур

Экскалибур - легендарный меч короля Артура, иногда также приписываемый магическим силам или связанный с законным суверенитетом Британии. Чтобы стать королем Великобритании, Алан решил создать Экскалибур. Есть какая-то действительно старая магия, которая позволяет Вам создать меч. В магическом заклинании имеется m слов, каждое из которых представлено некоторым целым числом wi. Чтобы наложить заклинание, Вам необходимо построить связный граф с n вершинами и m ребрами без петель и мультиребер. Веса ребер должны быть весами от магического заклинания. Другими словами, веса этого графа должны образовывать перестановку wi. В этом графе сумма ребер минимального остовного дерева должна равняться X. Минимальное остовное дерево - это неориентированный связный граф с n - 1 ребром без циклов, в котором сумма ребер минимально возможна.

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

Первая строка содержит 3 целых числа n, m, X (2n100, 0m1000, 0X4000). Вторая строка содержит m целых чисел wi(1wi40).

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

Если Экскалибур сздать нельзя, выведите -1. Иначе в первой строке выведите m. В каждой из следующих m строк выведите 3 целых числа u, v, c (1un, 1vn, uv, 1c40) – ребра графа. Веса ребер должны представлять собой некоторую перестановку входной последовательности wi.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
3 2 2
1 1
Выходные данные #1
2
1 2 1
2 3 1
Источник 2019 Fall KBTU OPEN, Задача E