Shohruh o`qishdan tashqari juda ko`plab joylardai shlaydi. U yashayotgan joyda N ta shahar bo`lib, har bir shahardan qolgan hamma shaharga borsa bo`ladi. Shohruhning uyi V – shaharda joylashgan. U ertalab uyidan chiqishdan oldin boradigan joylarini ro`yxatini tuzadi. Uning ro`yxati bo`yicha u T ta joyga berilgan tartibda  borishi kerak. Buning uchun u oldin X – shaharga borib kerakli narsalarni oladi va keyin Y – shaharga o`tadi. Shohruh vaqtni juda qadrlagani sabab rejadagi joylarni hammasiga minimal vaqtda borishni rejalashtirmoqda. Sizning vazifangiz Shohruh qancha vaqtini yo`lda o`tkazganini topishdan iborat.

Kiruvchima`luotlar

 N – shaharlarsoni(1≤N≤100).

N x N lik matritsa orqali shaharlarning bog`lanishi beriladi. 0 bo`lsa bog`lanish yo`q. Aks holda ikki shahar orasidagi o`tish vaqti berilgan bo`ladi. Qiymati 10⁶ dan oshmaydi.

V – Shohruhning uyi joylashgan shahar

T(1≤T≤100) – Shohruhning rejalashtirgan joylari soni

Keyin T ta qatorda X va Y (1≤X,Y≤N)sonlar beriladi

Chiquvchi ma`lumotlar:

Shohruhning yo`lda yo`qotgan minimal vaqtini chiqaring