Дороги в Байтляндії – 2
Відвідуючи острова Байтляндії на RoverLandi президент Бітик зрозумів, що жителі островів також хочуть відвідувати інші острови на своїх наземних транспортих засобах SonaL. Тому Бітику потрібно виділити бюджет на побудову двонаправлених мостів між островами. Архітектор надав президентові проекти майбутніх мостів, а президент уже повинен вибрати які мости будувати, так, щоб існував єдиний шлях між будь-якими двома островами. Зрозуміло, що Бітик хоче потратити якомога менше грошей (як ви пам'ятаєте, вартість будівництва зележить від довжини мосту).
Після цього жителям островів стало цікаво: яка довжина найкоротшого шляху між двома островами на SonaLi.
Вхідні дані
У першому рядку на вхід подається два натуральних числа: N (1 ≤ N ≤ 10^5) – кількість островів в країні, та M (1 ≤ M ≤ 10^5). У наступних M рядках по 3 натуральних числа: u, v, w (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ w ≤ 10^4), u, v – номери островів, які можна з’єднати мостом довжиною w.
У наступному рядку число q (1 ≤ q ≤ 10^7) – кількість жителів, які цікавляться найкоротишми відстанями, а у наступних q рядках номери островів, між якими треба знайти найкоротший шлях.
Вихідні дані
У першому рядку вартість побудови всіх мостів, або "Impossible", якщо з даних проектів не можна побудувати таку систему мостів, щоб існував шлях між будь-якими двома островами. Якщо мости побудувати можна, то у наступних q рядках відповіді на запити громадян.