Krallıq
King Kong Transilvaniyanın qorxulan, lakin ədalətli hökmdarıdır. Krallıq iki şəhərdən və N < 150 qəsəbədən ibarətdir, bəzi qəsəbələr arasında kəsişməyən yollar mövcuddur. Yollar ikitərəflidir və hər iki istiqamətdə səyahət etmək mümkündür. Kongun G < 353535 əsgəri var.
İki şəhər arasında keçi pendiri qaçaqmalçılığının artması səbəbindən, Kong əsgərlərini elə yerləşdirməlidir ki, bir şəhərdən digərinə əsgərlərdən keçmədən getmək mümkün olmasın. Əsgərlər qəsəbənin içində yerləşdirilə bilməz, lakin yolda, Kongun istədiyi qədər qəsəbəyə yaxın yerləşdirilə bilər. Eyni yolda istənilən sayda əsgər yerləşdirilə bilər. Lakin, əgər iki şəhərdən biri xarici ordu tərəfindən hücuma məruz qalarsa, kral bütün əsgərlərini tez bir zamanda hücuma məruz qalan şəhərə köçürməlidir. Əsgərləri elə yerləşdirin ki, bu səfərbərlik vaxtı minimum olsun.
Qeyd edək ki, əsgərlər heç bir şəhərdə və ya qəsəbədə yerləşdirilə bilməz. Şəhərlərin poçt indeksləri 95050 və 104729, qəsəbələrin isə 0 ilə N-1 arasında dəyişir. Hər hansı iki qəsəbə və ya şəhər arasında ən çox bir yol olacaq.
Giriş verilənləri
Giriş bir neçə test halını ehtiva edir. Hər test halının ilk sətri N, G və E dəyərlərini ehtiva edir, burada N və G yuxarıda göstərildiyi kimi müəyyən edilmişdir və E < 5000 yolların sayıdır. Sonra E sətir gəlir, hər biri üç tam ədəd ehtiva edir: A və B, son nöqtələrin poçt indeksləri və φ, yolda səyahət üçün tələb olunan vaxt, φ < 1000. Girişin son sətri tək 0 ehtiva edən bir sətirdir.
Çıxış verilənləri
Girişdəki hər test halı üçün mümkün olan ən yaxşı səfərbərlik vaxtını bir ondalık ilə çap edin. Əgər verilən əsgər sayı keçi pendirini dayandırmaq üçün kifayət deyilsə, "Impossible" yazın.