404504: GYM101521 H Pokemon GO

Be a Pokemon trainer! In Pokemon GO, you can collect eggs from Pokestops. An egg can be hatched by putting it in an incubator, followed by walking a certain distance in the real world.

Being a smart trainer, Ian is trying to find ways to maximize his egg hatching efficiency. The city has N pokestops, numbered 1 to N, and there are M two-way routes connecting pairs of Pokestops. The i^th route is L_i meters long. No two routes connect the same pair of Pokestops. Also, no route connect a Pokestop to itself. It is always possible to reach any Pokestop from a Pokestop.

Ian is now at Pokestop A and he wishes to arrive at Pokestop B after the walk. Help him find a path that is exactly K meters long. While he is allowed to visit a Pokestop zero or more times and use a route zero or more times, he cannot return in the middle of a route. There is no need to maximize the number of Pokestop visits.

The first line contains three integers N, M, K – the number of Pokestops, the number of routes, and the required path length respectively. (2 ≤ N ≤ 1000, , )

The second line contains two integers A and B – the starting and ending Pokestops. A and B are not necessarily different.

The next M lines describe the routes. Each line contains three integers X_i, Y_i, L_i, meaning that the route connects Pokestops X_i and Y_i and its length is L_i. (1 ≤ X_i, Y_i ≤ N, X_i ≠ Y_i, 1 ≤ L_i ≤ 10⁹)

If there is no path of exactly K meters long, output Impossible.

Otherwise output any valid path, which is the order of the Pokestops that Ian should visit.

4 4 2000
1 4
1 2 350
2 3 500
3 4 150
1 4 1600

1 2 3 2 3 4

3 3 5000
2 2
1 2 480
1 3 360
2 3 90

Impossible

The first sample corresponds to the image in the statement. The sample output path length = 350 + 500 + 500 + 500 + 150 = 2000 .

In the second sample, it is easy to see that there is no path of length 5000 because all route lengths are multiples of 30.