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