Важкий вантаж#4114
Великі вантажівки Джонсона Інк. - компанія, що спеціалізується на виробництві великих вантажівок. Їхня остання модель Годзіла V12 настільки велика, що кількість вантажу, який перевозиться самою вантажівкою, не обмежена. Існують лише вагові обмеження на дороги, по яким можна їздити.
Знаючи початкове та кінцеве місто, Вам потрібно визначити максимальне завантаження Годзіли V12, для якого усе ще буде існувати шлях між двома заданими містами.
Складаються з одного чи декількох тестів. Перший рядок кожного тесту містить два числа: кількість міст (2 \leq n \leq 200) та кількість відрізків доріг (1 \leq r \leq 19900), які і складають мережу доріг країни.
Далі йде рядків, кожен з яких описує одну дорогу, що з'єднує два міста, які задаються їхніми назвами, а також максимальну вагу, яку дозволено перевозити по цій дорозі. Назви міст містять не більше символів і не містять пропусків. Обмеження на вагу лежать у межах 0 - 10000. Усі дороги двосторонні.
Останній рядок кожного тесту містить назви двох міст: початкового та кінцевого. Останній рядок містить два нулі для та .
Для кожного тесту вивести три рядки:
рядок з повідомленням "Scenario #x", де - номер тесту
рядок з повідомленням "y tons", де - величина максимального завантаження вантажівки
порожній рядок якщо далі йде ще один тест
Приклад 1