Big Johnsson Trucks Inc. - компания, специализирующаяся на производстве больших грузовиков. Их последняя модель Godzilla V12 настолько велика, что количество груза, которое Вы можете перевозить, никогда не ограничивается самим грузовиком. Он ограничен только весовыми ограничениями, которые применяются к дорогам, по которым Вы хотите проехать.

Зная начальный и конечный город, определите максимальную загрузку Godzilla V12, чтобы все еще существовал путь между двумя указанными городами.

Входные данные

Содержит один или несколько тестов. Первая строка каждого теста содержит два целых числа: количество городов n (2 ≤ n ≤ 200) и количество участков дорог r (1 ≤ r ≤ 19900), составляющих уличную сеть.

Затем следуют r строк, каждая из которых описывает одну дорогу. Дорога задается названиями двух городов и ограничением по весу для грузовиков. Названия городов не длиннее 30 символов и не содержат пробелов. Веса являются целыми числами в диапазоне 0 .. 10000. По дорогам всегда можно двигаться в обоих направлениях.

Последняя строка теста содержит два названия города: начальный и конечный.

Входные данные завершаются двумя нулями для n и r.

Выходные данные

Для каждого теста выведите три строки:

• "Scenario #x" где x - номер теста;
• "y tons" где y - максимальная возможная загрузка;
• пустая строка если далее идет еще один тест;