SPOJ in Armenian

Թիմուրը որոշել է հետազոտել տիեզերքը։ Բարեբախտաբար, պարզվեց, որ այն շատ փոքր է. կա ընդամենը N մոլորակ։ Մոլորակների միջև ճամփորդելու համար օգտագործվում են զուգահեռ աշխարհներ, որոնց քանակը K է։ Յուրաքանչյուր մոլորակում յուրաքանչյուր զուգահեռ աշխարհի համար կա առավելագույնը մեկ անցակետ։ Մոլորակից մոլորակ անցումը տեղի է ունենում ակնթարթորեն և անվճար. Բավական է  ուղևորը  մտնի A մոլորակում  i-րդ զուգահեռ աշխարհի անցակետը և ակնթարթորեն կարող է դուրս ագալ B մոլորակում i-րդ զուգահեռ աշխարհի անցակետից։ Սակայն տվյալ մոլորակի մի անցակետից մեկ այլ անցակետ տեղափոխվելու համար պետք է օգտվել հին տեխնիկայից՝ ֆոտոնային օդանավից։ Օդանավի տոմսը յուրաքանչյուր մոլորակում յուրաքանչյուր երկու անցակետերի համար ունի իր արժեքը։

Թիմուրն ապրում է 1 համարի մոլորակում 1 համարի զուգահեռ աշխարհի անցակետի մոտ։ Նա պետք է հասնի N համարի մոլորակի K համարի զուգհեռ աշխարհի անցակետ։ Թիմուրը դա ուզում է անել զուգահեռ աշխարհներից մինիմալ անգամ օգտվելով (քանի որ դա վնասակար է առողջության համար) և մինիմալ գումար ծախսելով։ Ընդ որում առողջությունն ավելի կարևոր է քան գումարը։

Մուտքը

Առաջին տողում տրված է N մոլորակների քանակը (1 <= N <= 100), M անցակետերի քանակը (1 <= M <= 100000), K զուգահեռ աշխարհների քանակը (1 <= K <= 11): Հաջորդ M տողերից յուրաքանչյուրը պարունակում է 3 A, B, C թվեր և նկարագրում է մի անցուղի. A,B-ն մոլորակների համարներն են, C-ն զուգահեռ աշխարհի համարն է։

Ապա տրված են N մոլորակներից յուրաքանչյուրում անցակետերի միջև օդանավերով ճամփորդելու համար տոմսերի արժեքները։ Յուրաքանչյուր մոլորակի համար տրված է K տող, յուրաքանչյուրում՝ K ամբողջ թիվ, 1-ից 100 սահմեններում գտնվող։  i-րդ տողի j-րդ թիվը ցույց է տալիս, թե տվյալ մոլորակում i-րդ զուգահեռ աշխարհի անցակետից j-րդ զուգահեռ աշխհարհի անցակետ գնալում համար որքան է պետք վճարել։ Յուրաքանչյուր տողում թվերն իրարից անջատված են բացակներով։

Ելքը

Ելքում պետք է արտածել, իրարից մեկ բացակով անջատված, երկու թիվ՝ զուգահեռ աշխարհներից օգտվելու մինիմալ քանակը և մինիմալ գումարը։

Օրինակ

Մուտքը.
2 1 4
1 2 3
0 2 5 0
0 0 2 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 2
0 2 0 5
0 0 0 0

Ելքը.
1 8