Одностороння вулиця

Einbahnstraße (німецькою "вулиця з одностороннім рухом") — це вулиця, по якій транспортні засоби можуть рухатися лише в одному напрямку. Однією з причин введення вулиць з одностороннім рухом є забезпечення більш плавного руху транспорту через переповнені райони. Це особливо корисно в центрах міст, зокрема в старих містах, таких як Каїр і Дамаск. Ретельне планування гарантує, що можна дістатися до будь-якого місця, починаючи з будь-якої точки. Проте водіям доводиться ретельно планувати свій маршрут, щоб уникнути його подовження через односторонні вулиці. Досвідчені водії знають, що між будь-якими двома точками існує декілька шляхів. Більше того, між одними й тими ж двома місцями може бути кілька доріг. Знання найкоротшого шляху між будь-якими двома місцями є надзвичайно важливим! Це ще важливіше для транспортних засобів, якими складно маневрувати (сміттєвози, евакуатори тощо).

Ви щойно влаштувалися на нову роботу в компанію з евакуації автомобілів. У компанії є кілька евакуаторів, які стоять у гаражі компанії. Евакуатор піднімає передні або задні колеса зламаного автомобіля, щоб буксирувати його прямо назад до гаража компанії. Ви отримуєте дзвінки з різних районів міста щодо зламаних машин, які потрібно евакуювати. Автомобілі повинні буксируватися у порядку отримання викликів. Ваше завдання — порадити водіям евакуаторів найкоротший маршрут для збору всіх зламаних машин і доставки їх назад у гараж компанії. Наприкінці дня ви маєте повідомити керівництву загальну відстань, яку проїхали евакуатори.

Вхідні дані

Ваша програма буде тестуватися на одному або декількох тестах. У першому рядку кожного тесту містяться три числа $N$, $C$ та $R$, розділені одним або кількома пропусками. У місті є $N$ локацій з унікальними назвами, включаючи гараж компанії. $C$ — кількість зламаних автомобілів. $R$ — кількість доріг у місті. Зауважте, що 0 < N < 100, 0 \leq C < 1000 та R < 10000. У другому рядку записано C + 1 слів: перше — назва гаража компанії, решта — це місця розташування зламаних машин. Назва місця — це слово, яке містить не більше $10$ літер. Регістр літер має значення.

Після другого рядка слідуватимуть рівно $R$ рядків, кожен з яких описує одну дорогу. Дорога описується в одному з таких трьох форматів:

A -v -> B

A <-v - B

A <-v -> B

$A$ і $B$ — назви двох різних локацій, а $v$ — додатне ціле число, не більше $1000$, яке вказує на довжину дороги. Перший формат визначає вулицю з одностороннім рухом з $A$ до $B$, другий — з $B$ до $A$, останній — двосторонню вулицю між ними. $A$, стрілка та $B$ розділені одним або кількома пробілами.

Кінець тестів позначається рядком із трьома нулями (для $N$, $C$ та $R$).

Приклад тестового випадку наведено на ілюстрації нижче.