eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дороги Абсурдистана

Дороги Абсурдистана

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Народ Абсурдистана обнаружил как строить дороги только в прошлом году. После открытия каждый город решил построить свою дорогу, соединяющую свой город с некоторым другим городом. Каждая новая дорога может использоваться в обоих направлениях.

Абсурдистан полон удивительных совпадений. Для строительства дорог всем n городам потребовался всего один год. И что еще более удивительно, в конце концов можно было путешествовать из каждого города в любой другой город, используя недавно построенные дороги.

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

Вхідні дані

Для каждого теста:

  • Строка содержит число n (2n2000) - количество городов и дорог.

  • n строк по n чисел. j-ое число i-ой строки содержит кратчайшее расстояние между городами i и j. Все расстояния между двумя различными городами положительны и не более 10^6. Расстояние от i до i всегда равно 0, а расстояние от i до j равно расстоянию от j до i.

Вихідні дані

Для каждого теста вывести n строк с тремя целыми числами a b c описывающих дорогу между городами a и b (1a, bn) длины c (1c10^6), где ab. Если существует несколько решений, то вывести любое, дороги можно выводить в любом порядке. Гарантируется, что хотя бы одно решение всегда существует.

Между каждой парой тестов следует выводить пустую строку.

Приклад

Вхідні дані #1
4
0 1 2 1
1 0 2 1
2 2 0 1
1 1 1 0
4
0 1 1 1
1 0 2 2
1 2 0 2
1 2 2 0
3
0 4 1
4 0 3
1 3 0
Вихідні дані #1
2 1 1
4 1 1
4 2 1
4 3 1

2 1 1
3 1 1
4 1 1
2 1 1

3 1 1
2 1 4
3 2 3
Джерело 2013 ACM North Western European Regional Contest (NWERC), Ноябрь 24, Задача A