На доске нарисован граф-дерево из n вершин. Напомним, что неориентированный граф называется деревом, если он связен и не содержит циклов.
Каждая вершина графа покрашена в черный или белый цвет таким образом, что не существует двух вершин одного цвета, соединенных ребром. На каждом ребре записана его стоимость — неотрицательное целое число.
Плохой мальчик Вася подошел к доске и написал около каждой вершины v число sv — сумму стоимостей всех инцидентных этой вершине ребер, после чего он стер ребра и их стоимости с доски.
Ваша задача — восстановить исходное дерево по цветам вершин и числам sv.
Выходные данные
Выведите описание n - 1 ребер графа-дерева. Каждое описание — это тройка чисел vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 0 ≤ wi ≤ 109), где vi и ui — номера вершин, которые соединяет i-ое ребро, а wi — его стоимость. Обратите внимание, что должно выполняться условие cvi ≠ cui.
Гарантируется, что для любых входных данных существует по крайней мере один соответствующий этим данным граф. Если существует несколько решений, то выведите любое. Ребра разрешается выводить в любом порядке. Числа при выводе разделяйте пробелами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 3
1 2
0 5
|
3 1 3
3 2 2
|
|
2
|
6
1 0
0 3
1 8
0 2
0 3
0 0
|
2 3 3
5 3 3
4 3 2
1 6 0
2 1 0
|