Heavy Cargo

Big Johnsson Trucks Inc. manufactures very large trucks. Their latest model, the Godzilla V12, is so big that the amount of cargo it can carry is never limited by the truck itself — it is limited only by the weight restrictions of the roads along the route you drive.

Given a start city and a destination city, determine the maximum load the Godzilla V12 can carry so that a path between the two cities still exists. The load a route can bear equals the smallest weight limit among the roads on that route, and you may choose any route; report the largest such minimum over all possible routes.

The input contains one or more test cases. The first line of each test case has two integers: the number of cities $n$ ($2 \le n \le 200$) and the number of road segments $r$ ($1 \le r \le 19900$) in the road network.

Each of the next $r$ lines describes one road segment by naming the two cities it connects and its weight limit for trucks. City names are at most 30 characters long and contain no whitespace. Weight limits are integers from 0 to 10000. Every road can be travelled in both directions.

The last line of each test case contains two city names: the start city and the destination city.

The input ends with a line containing two zeros for $n$ and $r$; that line is not processed.

For each test case, print two lines: a line Scenario #x, where $x$ is the test case number (starting from 1), and a line y tons, where $y$ is the maximum possible load. Separate consecutive test cases with one blank line.