Дороги в Байтляндії – 2#4466
Під час візиту на острови Байтландії президент Бітик зрозумів, що мешканці також бажають подорожувати своєю країною на автомобілях SonaL. Для цього Бітику потрібно виділити новий бюджет на будівництво двосторонніх мостів. Архітектор надав президентові запропоновані проєкти мостів. Тепер президент має обрати, які мости будувати так, щоб усі острови були з'єднані. Звісно, Бітик хоче витратити якомога менше коштів.
Після спорудження мостів жителі островів зацікавлені у довжині найкоротшого маршруту між будь-якими двома островами.
У першому рядку знаходяться два додатні цілі числа (1 \leq N \leq 10^5) — кількість островів у країні, та (1 \leq M \leq 10^5) — кількість запропонованих мостів. Кожен з наступних рядків містить три додатні цілі числа , , (1 \leq u, v \leq N, u \neq v, 1 \leq w \leq 10^4), що означає, що можна збудувати міст довжиною між островами та .
Наступний рядок містить додатне ціле число (1 \leq q \leq 10^7) — кількість запитів. Кожен з наступних рядків містить по два номери островів. Для кожного запиту знайдіть довжину найкоротшого шляху між даною парою островів.
У першому рядку виведіть загальну вартість всіх нових збудованих мостів, або Impossible, якщо неможливо побудувати таку систему мостів, щоб усі острови були з'єднані. Якщо побудувати мости можливо, то для кожного з наступних рядків виведіть відповідь на кожен запит.
Приклад 1