Королевство
Кинг Конг — грозный, но справедливый правитель Трансильвании. Королевство состоит из двух городов и N < 150 городков, соединенных непересекающимися дорогами. Дороги двусторонние, и время на их преодоление одинаково в обоих направлениях. У Конга есть G < 353535 солдат.
Из-за увеличившегося контрабандного провоза козьего сыра между двумя городами, Конг должен разместить своих солдат на некоторых дорогах так, чтобы никто не мог пройти из одного города в другой, не встретив солдата. Солдаты не могут быть размещены внутри городка, но могут находиться на дороге, насколько близко к городку, как пожелает Конг. На одной дороге может быть размещено любое количество солдат. Однако, если на один из двух городов нападет иностранная армия, король должен иметь возможность быстро перебросить всех своих солдат в атакуемый город. Помогите ему разместить солдат так, чтобы время мобилизации было минимальным.
Обратите внимание, что солдаты не могут быть размещены в любом из городов или городков. У городов почтовые индексы 95050 и 104729, тогда как у городков почтовые индексы от 0 до N-1. Между любой парой городков или городов может быть не более одной дороги.
Входные данные
Вход содержит несколько тестов. Первая строка каждого теста содержит N, G и E, где N и G определены выше, а E < 5000 — количество дорог. Далее следуют E строк, каждая из которых содержит три целых числа: A и B, почтовые индексы конечных точек, и φ, время, необходимое для преодоления дороги, φ < 1000. Последняя строка ввода содержит одну строку с числом 0.
Выходные данные
Для каждого теста на входе выведите лучшее возможное время мобилизации с одной десятичной точностью. Если заданного количества солдат недостаточно, чтобы остановить контрабанду козьего сыра, выведите "Impossible".