Q - Pump Fiction

Amsterdam has N (2<=N<=100) intersections and M one-way street segments, each connecting two distinct intersections (two-way streets are represented by two one-way segments, one going each way). Vincent rents a car from the Amsterdam Car Mechanics (ACM) and goes to intersection D to do Marcellus' dirty work. When he is done, he finds that his car has (0<=L<=100) units of gas left. He wants to drive it to intersection R. The car is a mess, and he does not want anybody to see it, so he must drive without stopping (that means he can not even stop at a gas station). Time is not an issue, but instead, when he gets to intersection R, he wants the car to have as little fuel left as possible. The reasons for that are complicated, and we won't get into that.

Given a description of the city (the list of one-way street segments and how many units of fuel are burned by driving on that segment), your task is to determine the smallest amount of fuel that Vincent can have in the car's tank when he arrives at intersection R

Input

The input will consist of a number of test cases. Each case begins with a line containing the numbers N, M, D, R and L. Intersections are numbered from 0 to N-1. The next M lines contain 3 numbers each, u, v and w, which stand for "driving from intersection u to intersection v, the car burns w units of fuel." w will be a positive integer.

Output

For each test case, output the amount of fuel left, then a colon, a space and a space-separated list of intersections - the path Vincent needs to take. In cases when there are several paths giving the same minimum value, print the lexicographically smallest path. If Vincent can not possibly get to R, print "TROUBLE" on the line by itself instead. Note that there should be no trailing spaces on any of the output lines.

Sample input

3 4 0 2 9
0 1 10
1 2 10
0 2 3
2 0 2
5 6 4 1 16
4 2 10
4 3 3
3 2 3
2 0 2
0 1 3
2 1 10
2 1 0 1 5
0 1 6

Sample output

1: 0 2 0 2
0: 4 3 2 1
TROUBLE