Дороги Абсурдистану
Народ Абсурдистану лише минулого року навчився будувати дороги. Після цього кожне місто вирішило прокласти дорогу, що з'єднує його з іншим містом. Кожна нова дорога є двосторонньою.
Абсурдистан славиться своїми дивовижними збігами. Для будівництва доріг усім 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. Якщо існує кілька рішень, виведіть будь-яке; дороги можна виводити в будь-якому порядку. Гарантовано, що хоча б одне рішення завжди існує.
Між кожною парою тестів слід виводити порожній рядок.