• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

مردم سنبلستان تازه برای اولین بار سال گذشته کشف کردند که چگونه در کشورشان جاده بسازند. نماینده هر شهر کلنگ احداث جاده‌ای را برای شهرش زد که آن را به شهری دیگر متصل کند. هر یک از $N$ شهر دقیقاً یک سال زمان صرف کرد تا جاده خود بسازد. جاده‌ها برای استفاده دو طرفه ساخته شدند. نکته عجیب این بود که بعد از این یک سال، بین هر دو شهر مسیری وجود داشت. اخیراً شما قصد عزیمت به سنبلستان را دارید و برای اطمینان یک راهنمای توریست سنبلستان خریدید. اما متوجه شدید که این راهنما نقشه راه‌های کشور را ندارد، بلکه تنها شامل یک جدول بزرگ از کوتاهترین فاصله بین هر دو شهر با استفاده از جاده‌های احداث شده است. شما می‌خواهید نقشه $N$ جاده را بیابید و برای این کار از جدول کوتاه‌ترین فاصله ها استفاده می‌کنید. یک جدول از کوتاه‌ترین فاصله بین هر دو شهر سنبلستان با استفاده از $N$ جاده ساخته شده در سال پیش را دریافت می‌کنید. از این جدول، باید شبکه‌ی جاده‌های سنبلستان را بازسازی کنید. ممکن است شبکه‌های متعددی با $N$ جاده براساس یک جدول کوتاه‌ترین فاصله، وجود داشته باشد. بنابراین هر یک از این شبکه‌ها صحیح است.

ورودی

خط اول شامل یک عدد صحیح $N$ ($2 \le N \le 2000$) است که تعداد شهرها و جاده‌ها را مشخص می‌کند. در ادامه $N$ خط شامل $N$ عدد می‌آید. عدد $j$ام از خط $i$ام، کوتاه‌ترین فاصله بین شهر $i$ تا شهر $j$ است. فاصله بین دو شهر متمایز یک عدد مثبت بوده و مقدارش حداکثر 1,000,000 است. فاصله بین شهر $i$ تا شهر $i$ برابر صفر بوده و همچنین فاصله بین شهر $i$ تا شهر $j$ با فاصله بین شهر $j$ تا شهر $i$ برابر است.

خروجی

تعداد $N$ خط چاپ کنید که هر خط شامل سه عدد صحیح $a$ و $b$ و $c$ است به این معنی که یک جاده بین شهر $a$ ($1 \le a \le N$) و شهر $b$ ($1 \le b \le N$) با فاصله $c$ ($1 \le c \le 1,000,000$) وجود دارد ($a$ مخالف $b$ است). اگر راه‌حل‌های متعددی موجود است می‌توانید هر یک از آنها را با جاده‌هایشان چاپ کنید. همواره حداقل یک راه‌حل وجود دارد. بین هر دو نمونه تست، یک خط خالی چاپ کنید.

مثال

ورودی نمونه

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

خروجی نمونه

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