Heavy Transportation

Hugo Heavy is expanding his business. He has to move a giant steel crane from where his customer built it to where it is needed, and every street along the route must be able to carry the crane's weight.

He has a map of the city listing every street and bridge together with its weight limit, but he has no idea how heavy the crane may become for the route to still support it. Working that out is your job.

The city has $n$ crossings, numbered from $1$ to $n$. Streets connect the crossings, and each street has a maximum weight it can carry. Find the maximum weight that can be transported from crossing $1$ (Hugo's place) to crossing $n$ (the customer's place). This is the value of the route from $1$ to $n$ whose smallest street weight limit is as large as possible. Every street can be travelled in both directions, and you may assume at least one route from $1$ to $n$ always exists.

The first line contains the number of scenarios (city maps).

Each scenario starts with a line containing two integers $n$ and $m$: the number of crossings ($1 \le n \le 1000$) and the number of streets. Each of the next $m$ lines contains three integers $a$, $b$, and $w$, describing a street between crossings $a$ and $b$ with maximum allowed weight $w$ ($1 \le w \le 1000000$). There is at most one street between any pair of crossings.

For each scenario, print a line Scenario #i:, where $i$ is the scenario number starting at $1$, followed by a line containing the maximum weight that can be transported from crossing $1$ to crossing $n$. Print a blank line between consecutive scenarios.