Дороге метро#6922
Пітер живе в Дорогому місті, одному з найдорожчих міст світу. Пітер не має достатньо грошей, щоб купити машину, а автобуси в Дорогому місті досить погані, тому він користується метро, щоб їхати на роботу. Досі метро було дуже дешевим: ви могли подорожувати куди завгодно, маючи лише один $2 квиток. Минулого місяця менеджери вирішили, що це занадто дешево, тому вони винайшли EFS (Expensive Fare System). За допомогою цієї системи користувачі можуть купувати місячні квитки лише між сусідніми станціями, що дозволяє їм пересуватися між цими станціями будь-яку кількість разів. Ціна місячного квитка на станції різна, тому до рішення про те, які квитки купити, потрібно підходити ретельно.
З попереднім планом метро найдешевшим способом подорожі від Пікаділлі до Вікторії та Квінсвею було придбати місячний квиток на Пікаділлі-Вікторія та Квінсвей-Вікторія загальною вартістю $12.
Пітер — продавець, тому йому потрібно мати можливість доїхати до будь-якої частини міста. Він хоче витрачати якомога менше грошей, і тут на допомогу приходите ви. Він найняв вас, щоб ви написали програму, яка, враховуючи список станцій, тарифи місячних квитків між парами станцій і станцією, найближчою до дому Пітера, повертає мінімальну суму грошей, яку Пітер має витратити, щоб поїхати до будь-якої іншої станції. Ця програма також має повертати значення, якщо неможливо дістатися від домашньої станції Пітера до всіх інших, тому що в цьому випадку Пітер почне розглядати використання автобусів...
Вхідні дані складаються з кількох тестових випадків. Тестовий випадок починається з рядка, що містить два цілі числа: 1 \le s \le 400 (кількість станцій) і 0 \le c \le 79800 (кількість з'єднань), розділених одним пробілом. Далі йдуть рядків, кожен з яких містить назву станції метро. Ці назви є рядками символів (великі або малі літери) без знаків пунктуації чи пробілів і мають максимальну довжину символів. Після назв станцій надається рядків, які показують з'єднання між станціями. З'єднання дозволяє людям подорожувати від однієї станції до іншої в обох напрямках. Кожне з'єднання представлено у вигляді двох рядків, що вказують назви станцій, і одного додатного цілого числа, що задає вартість місячного квитка; усі значення розділені одним пробілом. Усі назви станцій, які фігурують у з'єднаннях, вже згадувалися у списку станцій. Всі з'єднання різні, і не існує жодного з'єднання для переходу від станції до самої себе. Тестовий випадок закінчується рядком із назвою станції, з якої Пітер має дістатися до всіх інших станцій.
Ввід закінчується фантомним тестом , який обробляти не потрібно.
Для кожного тестового випадку у відповідь виведіть рядок з цілим числом — мінімальна місячна вартість, яку Пітер має заплатити за поїздку від цієї станції до всіх інших, або Impossible, якщо не можна доїхати до всіх станцій.
Приклад 1