Jill's Tour Paths

Every year Jill rides a bicycle tour between two villages. Several routes connect the two villages, but there is an upper limit on the distance she wants to ride. Given a map of the region that shows the villages, the roads between them, and the distance along each road, Jill wants a list of the routes between the two chosen villages that meet her distance requirement. Write a program that produces this list in increasing order of distance.

We make the following assumptions.

• At most one road connects any pair of villages, and this road is two-way and has a positive distance.
• No road leads from a village directly back to the same village.
• Jill only cares about a one-way trip. She is not concerned about returning to the village where she starts her tour.
• Jill does not visit any village more than once during the tour.
• The farthest Jill will ever travel is 9999 units.

The input contains several cases. Each case holds a route map, the start and destination villages, and the maximum distance Jill is willing to ride.

Each case appears as integers separated by blanks or ends of lines. Their order and meaning is as follows.

• NV: the number of villages on the route map. It is no larger than 20.
• NR: the number of roads on the route map. Each road connects a distinct pair of villages.
• NR triples C1, C2, DIST, one for each road. C1 and C2 are the two villages the road connects, and DIST is the distance between them along that road.
• SV, DV: the numbers of the start and destination villages. The villages are numbered 1 to NV, and SV differs from DV.
• MAXDIST: the maximum distance Jill is willing to ride one way.

A single integer -1 follows the data for the last case.

For each case print Case k: on the first line, where k counts the cases from 1. Then list the routes Jill might take, one per line, with the length of the route in front. Order the routes by length, shortest first. Routes of equal length are ordered by their village numbers, compared one position at a time, smaller first.

A route line starts with one space, then the length of the route, then a colon, and then a space and the village number for each village on the route. A route of length 4 through villages 1, 2 and 3 prints as 4: 1 2 3.

When no route meets the limit, print NO ACCEPTABLE TOURS with the same leading space.

Separate the output for two consecutive cases with a single blank line.