Trucking

A local trucking company wants to transport goods on a cargo truck from one place to another. On each trip it wants to carry as much cargo as possible. Unfortunately the shortest route cannot always be used: some roads have obstacles (such as bridge overpasses or tunnels) that limit the height of the cargo that can pass. So the company first wants to carry as much as possible on a trip, and then, among all routes that can carry that amount, choose the shortest one.

For a given cargo truck, maximizing the height of the cargo is equivalent to maximizing the amount of cargo carried. For safety, the truck itself also has a height limit that cannot be exceeded.

In other words, the maximum height of cargo that can be carried is the smaller of the truck's height limit and the minimum height limit among the roads on the route. First find this maximum height, then find the length of the shortest route that uses only roads which allow cargo of that height.

The input consists of several cases. Each case begins with two integers $C$ and $R$ on one line, separated by a space: the number of cities $C$ and the number of roads $R$. There are at most 1000 cities, numbered from 1. This is followed by $R$ lines, each giving the two city numbers connected by a road, the maximum height allowed on that road, and the length of that road. The maximum height of each road is a positive integer, except that a height of $-1$ means the road has no height limit. The length of each road is a positive integer at most 1000. Every road can be travelled in both directions, and there is at most one road connecting any distinct pair of cities. Finally, the last line of each case gives the start and end city numbers together with the height limit of the cargo truck (a positive integer). The input terminates when $C = R = 0$.

For each case, first print Case X:, where $X$ is the case number starting from 1. If the destination is reachable, print maximum height = H on the next line (where $H$ is the maximum cargo height), and print length of shortest route = L on the following line (where $L$ is the length of the shortest route). If the end city cannot be reached from the start city, print cannot reach destination on the line after Case X:. Print a blank line between the output of consecutive cases.