Absurdistan yolları#7013
Absurdistan sakinləri yol tikməyi yalnız keçən il öyrənmişlər. Bu kəşfdən sonra hər şəhər başqa bir şəhərlə onu birləşdirən dəqiq bir yol tikməyə qərar vermişdir. Tikilmiş hər yoldan hər iki istiqamətdə istifadə etmək mümkündür.
Absurdistan heyrətamiz təsadüflərlə doludur. Bütün şəhərin öz yollarını tikməsi üçün dəqiq bir il lazım olmuşdur. Üstəlik, bütün yollar tikildikdən sonra, yalnız yeni yollardan istifadə edərək istənilən şəhərdən istənilən başqa şəhərə çatmaq mümkün olmuşdur.
Siz yeni yolları göstərən ölkə xəritəsi olmayan bir turist bələdçisi almısınız. Bunun əvəzinə orada yeni yollar üzrə hesablanmış hər şəhər cütü arasındakı ən qısa məsafələrin böyük bir cədvəli verilmişdir.
Siz hansı şəhər cütlərinin yollarla birləşdirildiyini və bu yolların hər birinin uzunluğunu müəyyən etmək istəyirsiniz. Başqa sözlə, ən qısa məsafələr cədvəli əsasında yeni yolun xəritəsini bərpa etmək istəyirsiniz.
Hər test üçün:
Birinci sətirdə şəhərlərin və yolların sayı olan (2 \le n \le 2000) tam ədədi verilmişdir.
Sonrakı sətirin hər birində tam ədəd verilmişdir. -ci sətirdəki -ci ədəd yeni yollardan istifadə edərək şəhərindən şəhərinə qədər olan ən qısa məsafədir. İstənilən iki fərqli şəhər arasındakı məsafə müsbətdir və 10^6-dan artıq deyil. şəhərindən özünə qədər olan məsafə həmişə -a bərabərdir, şəhərindən şəhərinə qədər olan məsafə isə şəhərindən şəhərinə qədər olan məsafə ilə üst-üstə düşür.
Hər test üçün sətir çap edin, hər sətirdə , və tam ədədləri olsun ki, bu, və b~(1 \le a, b \le n) şəhərləri arasında uzunluğu c~(1 \le c \le 10^6) olan bir yolun mövcud olduğunu bildirsin, burada a \ne b.
Əgər bir neçə həll mövcuddursa, onlardan istənilənini çap edin. Yolları istənilən sırada çap etmək olar. Ən azı bir düzgün həllin mövcud olduğu təmin edilir.
Hər iki ardıcıl test arasında boş sətir çap edin.
Nümunə 1