Дороги Абсурдистану#7013
Жителі Абсурдистану навчилися будувати дороги тільки минулого року. Після цього відкриття кожне місто вирішило побудувати рівно одну дорогу, що з'єднує його з іншим містом. Кожну побудовану дорогу можна використовувати в обох напрямках.
Абсурдистан повний дивовижних збігів. Усім містам знадобився рівно один рік, щоб побудувати свої дороги. Більш того, після того як усі дороги були побудовані, виявилося можливим дістатися з будь-якого міста до будь-якого іншого, використовуючи лише нові дороги.
Ви купили туристичний путівник, у якому немає карти країни з новими дорогами. Натомість він містить велику таблицю найкоротших відстаней між кожною парою міст, обчислених за новими дорогами.
Ви хочете визначити, які пари міст з'єднані дорогами і якою є довжина кожної з цих доріг. Іншими словами, ви хочете відновити карту з нових доріг за таблицею найкоротших відстаней.
Для кожного тесту:
У першому рядку міститься ціле число (2 \le n \le 2000) — кількість міст і доріг.
Наступні рядків містять по цілих чисел. -е число в -му рядку — це найкоротша відстань від міста до міста , використовуючи нові дороги. Відстань між будь-якими двома різними містами додатна і не перевищує 10^6. Відстань від міста до самого себе завжди дорівнює , а відстань від міста до міста збігається з відстанню від міста до міста .
Для кожного тесту виведіть рядків, кожен з яких містить три цілих числа , і , що означають, що між містами і b~(1 \le a, b \le n) існує дорога довжини c~(1 \le c \le 10^6), де a \ne b.
Якщо існує декілька розв'язків, виведіть будь-який з них. Дороги можна виводити в будь-якому порядку. Гарантується, що існує хоча б один допустимий розв'язок.
Виведіть порожній рядок між кожними двома послідовними тестами.
Приклад 1