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