Kādas valsts iedzīvotāji dzīvo uz n salām. Salas ir sanumurētas ar naturāliem skaitļiem no 1 līdz n.
Starp dažām no tām ir nodibināta kuģīšu satiksme.
Satiksme ir organizēta tā, ka no katras salas ir iespējams tikt uz katru citu izmantojot tikai kuģīšu satiksmi (ja starp attiecīgajām salām nav tiešās satiksmes, tad pārsēžoties).
Kuģīšu dažādo tipu dēļ var izrādīties, ka ne vienmēr tiešā satiksme ir arī tā ātrākā.

Tā, piemēram, ja ir 3 salas un brauciens no pirmās uz otro salu aizņem 30 minūtes, no otrās uz trešo - 15 minūtes, bet no pirmās uz trešo - 50 minūtes, tad no pirmās uz trešo salu visātrāk iespējams nokļūt 45 minūtēs (jābrauc vispirms uz otro salu).
Zināms, ka katrs kuģītis kursē tikai starp divām noteiktām salām. Starp katrām divām salām kursē ne vairāk kā viens kuģītis.

Uzrakstiet programmu, kas nosaka, kāds mazākais laiks nepieciešams, lai no katras salas nokļūtu uz jebkuru citu!
Laiku, kas jāpavada, gaidot kuģīti, nav jāņem vērā.

Ievaddatu pirmajā rindā doti divi naturāli skaitļi - salu skaits n (n<=50) un kuģīšu maršrutu skaits k (k<n(n-1)/2).
Nākošajās k faila rindās doti kuģīšu maršrutu apraksti - pa vienam maršruta aprakstam katrā rindā.
Katra maršruta apraksts ir formā

x y brauciena laiks minūtēs

, kur x un y - to salu numuri, starp kurām kursē dotā maršruta kuģītis.
Nevienam maršrutam brauciena laiks nepārsniedz 100 minūtes.
Starp katriem diviem blakus skaitļiem atrodas viens tukšumsimbols. Katra maršruta apraksts failā dots tieši vienreiz.

Izvaddatiem jāsatur tieši n rindas.
Katrā rindā jāizvada n veseli skaitļi, kas atdalīti ar tukšumsimboliem. i-tajā rindā j-tais izvadītais skaitlis atbilst mazākajam laikam minūtēs, kāds nepieciešams, lai no i-tās salas nokļūtu līdz j-tajai salai.

Uzdevums izmantots Latvijas 14.informātikas olimpiādes I (skolas) kārtā.
Autori: K.Boitmanis, M.Opmanis