A :: Azeroth

Time Limit: 10 Seconds    Memory Limit: 32768 KB
Special Judge

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

Input

    ورودی از چند نمونه تشکیل شده‌است. خط اول هر نمونه، N است که2000   2≤N≤بیان‌گر تعداد شهر‌های ازراث است. سپس N خط با N  عدد در هر خط می‌آید. عدد jام در خط iام  نشان‌دهنده‌ی  کوتاه‌ترین فاصله بین شهر i و شهر j است. فاصله‌ها مثبت هستند و حداکثر ۱۰۰۰۰۰۰ هستند. ورودی‌ها تا پایان فایل ادامه دارد.

Output

برای هر نمونه N خط چاپ کنید که به صورت ‘a b c’ باشد و a و b شماره‌ی شهر است و c طول جاده‌ی بین آن دو شهر را نشان می‌دهد. در صورتی که چند جواب وجود داشته باشد، هر یک را که خواستید چاپ کنید. تضمین می‌شود که حداقل یک جواب وجود دارد. بین هر نمونه یک خط خالی چاپ کنید.

طول جاده‌ی بین آن دو شهر را نشان می‌دهد. در صورتی که چند جواب وجود داشته باشد، هر یک را که خواستید چاپ کنید. تضمین می‌شود که حداقل یک جواب وجود دارد. بین هر نمونه یک خط خالی چاپ کنید.

Sample Input

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

Sample Output

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

Submit