Экскалибур
Экскалибур
Экскалибур - легендарный меч короля Артура, иногда также приписываемый магическим силам или связанный с законным суверенитетом Британии. Чтобы стать королем Великобритании, Алан решил создать Экскалибур. Есть какая-то действительно старая магия, которая позволяет Вам создать меч. В магическом заклинании имеется m слов, каждое из которых представлено некоторым целым числом wi
. Чтобы наложить заклинание, Вам необходимо построить связный граф с n вершинами и m ребрами без петель и мультиребер. Веса ребер должны быть весами от магического заклинания. Другими словами, веса этого графа должны образовывать перестановку wi
. В этом графе сумма ребер минимального остовного дерева должна равняться X. Минимальное остовное дерево - это неориентированный связный граф с n - 1 ребром без циклов, в котором сумма ребер минимально возможна.
Входные данные
Первая строка содержит 3 целых числа n, m, X (2 ≤ n ≤ 100, 0 ≤ m ≤ 1000, 0 ≤ X ≤ 4000). Вторая строка содержит m целых чисел wi
(1 ≤ wi
≤ 40).
Выходные данные
Если Экскалибур сздать нельзя, выведите -1. Иначе в первой строке выведите m. В каждой из следующих m строк выведите 3 целых числа u, v, c (1 ≤ u ≤ n, 1 ≤ v ≤ n, u ≠ v, 1 ≤ c ≤ 40) – ребра графа. Веса ребер должны представлять собой некоторую перестановку входной последовательности wi
.
3 2 2 1 1
2 1 2 1 2 3 1