Macəra#231
Hər kəs Indiana Consun əfsanəvi macəralarını tanıyır. Hər zamankı kimi, Cons macəra axtarışında çətin bir vəziyyətə düşür. İndi o, qədim Hindistan məbədindədir. Məbədin zalının divarında məbədin xəritəsi təsvir olunub. Məbəd - yalnız bir istiqamətdə hərəkət etmək mümkün olan dəhlizlərlə (koridorlarla) birləşdirilmiş otaqlardan ibarətdir.
Qədim dastanlara görə, kimsə ya bütün otaqlardan keçərsə, ya da xəzinəni taparsa, məbəd dağılır və azadlığa çıxmaq mümkün olur. Həmçinin məlumdur ki, istənilən bir otağa daxil olmaq və ya oradan çıxmaq bu otağın tavanının dağılmasına səbəb olur və gələcəkdə bu otaqdan keçmək mümkün olmur. Xəritədə məbədin bütün otaqları, aralarındakı tunellər və hər bir otaqda xəzinə olma ehtimalı göstərilir.
Indiana da hər kəs kimi tənbəldir və bu məsələni həll etməyi sizdən xahiş edir. Tünellərdən keçməklə gözlənilən orta yolu minimallaşdırmaq lazımdır. O, həmçinin istənilən otağa teleportun mümkün olduğunu bildirib.
Siz bütün otaqları əhatə edən minimum gözlənilən məsafəni verən yolu tapmalısınız. Əgər bütün otaqları əhatə edən belə yol yoxdursa, Consu məlumatlandırmaq lazımdır; belə halda, o, məbəddən heç vaxt çıxa bilməyə bilər.
Giriş faylında bir neçə test var. Hər bir testdə məbəd xəritəsi təsvir olunur. Hər testin birinci sətrində 1 \leq N \leq 100 — məbəddəki otaqların sayı verilir. Sonra hər birində ədəd a_{ij} (|a_{ij}| < 1000) olan sətr gəlir. Əgər a_{ij} -ci sətrin -ci mövqeyindədirsə, bu, -ci otaqdan -ci otağa uzunluğu a_{ij} olan tunel olduğunu göstərir. Əgər a_{ij} sıfırdan kiçikdirsə, bu, tunelin tıxanmış olduğunu və istifadə mümkün olmadığını bildirir. Sonrakı sətirdə ədəd p_i verilir. p_i -ci otaqda xəzinənin olma ehtimalıdır.
Sonuncu testdə N = 0-dır və emal olunmamalıdır.
Hər test üçün gözlənilən məsafəni onluq nöqtədən sonra üç rəqəm olmaqla verin. Əgər bütün otaqları əhatə edən yol yoxdursa, çıxışa -1 yazın.
Nümunə 1