Дороги Абсурдистана
Народ Абсурдистана обнаружил как строить дороги только в прошлом году. После открытия каждый город решил построить свою дорогу, соединяющую свой город с некоторым другим городом. Каждая новая дорога может использоваться в обоих направлениях.
Абсурдистан полон удивительных совпадений. Для строительства дорог всем n городам потребовался всего один год. И что еще более удивительно, в конце концов можно было путешествовать из каждого города в любой другой город, используя недавно построенные дороги.
Вы купили справочник туриста, в котором нет карты страны с новыми дорогами. Он содержит только огромную таблицу с кратчайшими расстояниями между всеми парами городов, использующими недавно построенные дороги. Вы хотели бы знать, между какими парами городов существуют дороги и какова их длина, потому что Вы хотите восстановить карту n недавно построенных дорог из таблицы кратчайших расстояний.
Входные данные
Для каждого теста:
Строка содержит число n (2 ≤ n ≤ 2000) - количество городов и дорог.
n строк по n чисел. j-ое число i-ой строки содержит кратчайшее расстояние между городами i и j. Все расстояния между двумя различными городами положительны и не более
10^6. Расстояние от i до i всегда равно 0, а расстояние от i до j равно расстоянию от j до i.
Выходные данные
Для каждого теста вывести n строк с тремя целыми числами a b c описывающих дорогу между городами a и b (1 ≤ a, b ≤ n) длины c (1 ≤ c ≤ 10^6), где a ≠ b. Если существует несколько решений, то вывести любое, дороги можно выводить в любом порядке. Гарантируется, что хотя бы одно решение всегда существует.
Между каждой парой тестов следует выводить пустую строку.