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ā.
Teksta faila salas.in 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
Teksta failam salas.out 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.
| salas.in | salas.out |
3 3 2 3 15 1 3 50 2 1 30 |
0 30 45 30 0 15 45 15 0 |