Beytlandiyada Yollar – 2#4466
ByteLandia adalarına səfər edərkən, Prezident Bitik orada yaşayanların da ölkələrində SonaL nəqliyyat vasitələrindən istifadə edərək səyahət etmək istədiklərini öyrəndi. Bunun üçün Bitik iki istiqamətli körpülərin tikintisi üçün yeni büdcə ayırmalıdır. Memar prezidentə təklif olunan körpü layihələrini təqdim etdi. İndi prezident hansı körpülərin tikiləcəyini seçməlidir ki, bütün adalar bir-biri ilə birləşsin. Əlbəttə, Bitik mümkün qədər az pul xərcləmək istəyir.
Körpülər tikildikdən sonra adalılar istənilən iki ada arasında ən qısa marşrutun uzunluğunu bilmək istəyirlər.
Birinci sətrdə iki müsbət tam ədəd (1 \leq N \leq 10^5) — ölkədəki adaların sayı və (1 \leq M \leq 10^5) — təklif olunan körpülərin sayı verilib. Sonrakı sətrin hər birində üç müsbət tam ədəd , , (1 \leq u, v \leq N, u \neq v, 1 \leq w \leq 10^4) verilib, bu da və adaları arasında uzunluğu olan körpü tikməyin mümkün olduğunu bildirir.
Növbəti sətirdə bir müsbət tam ədəd (1 \leq q \leq 10^7) — sorğuların sayı verilir. Növbəti sətrin hər birində isə iki ada nömrəsi verilir. Hər sorğu üçün, verilmiş iki ada arasında ən qısa yolun uzunluğunu tapın.
Birinci sətirdə tikilən bütün yeni körpülərin ümumi dəyərini, əgər bütün adaları birləşdirən körpü sistemi qurmaq mümkün deyilsə, **Impossible** çap edin. Əgər körpüləri tikmək mümkündürsə, onda növbəti sətrin hər birində hər sorğu üçün cavabı çap edin.
Nümunə 1