314. Shortest Paths

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



You are given a graph with one vertex marked as source s and one as destination t. Each edge of the graph has a positive length. Find the shortest path from s to t. Then find the second-shortest path (the shortest one of all the paths from s to t except the one you've just found). Then the third-shortest, and so on. Output the lengths of first k such paths.

Note that these paths may not be simple, i.e. they may contain some vertex or edge several times (see the 2nd example).

Input
The first line of the input file contains n, the number of vertices of the graph, m, the number of edges of the graph, and k, the number of paths sought (2 ≤ n ≤ 10000, 2 ≤ m ≤ 50000, 2 ≤ k ≤ 10000).

The second line of the input file contains s and t (integers between 1 and n, inclusive, s != t).

The next m lines contain the descriptions of the edges, each description consisting of three integer numbers: a b c, denoting the edge from a to b with length c (1 ≤ a,b ≤ n, a != b, 1 ≤ c ≤ 1000). There may be more than one edge for the same a and b.

Output
Output k integer numbers in non-decreasing order — the lengths of the paths. In case there are less than k different paths from s to t, output 
NO
instead of the lengths of all non-existent paths.

Example(s)
sample input
 
sample output
 
4 5 5
1 4
1 2 1
2 3 1
3 4 1
1 3 1
2 4 1

2
2
3
NO
NO


sample input
 
sample output
 
4 4 5
1 4
1 2 10
2 3 10
3 4 10
3 2 10

30
50
70
90
110


sample input
 
sample output
 
2 2 10
1 2
1 2 5
2 1 7

5
17
29
41
53
65
77
89
101
113