Do you remember Kelvin in the Team Qualification Contest this year? The troublesome student who aimed not to score the best, but some (lower) specific score instead?
Well, he just came back with more trouble!!
The thing is, there are many routes he can take to get to school. But he (possibly) doesn't want to take the fastest one! Given a directed graph that represents all the nodes and roads in Kelvin's consideration, he'd like to know what is the k-th shortest one, where k is given?
Ahh.. one more thing. Kelvin is trouble some, but he is not completely stupid! So he will never go across the same node twice in a route. i.e. All the routes in consideration must not have duplicate mid/endpoints.
The input consists of multiple datasets (terminated by EOF), each in the following format.
n m k s t
v1 u1 l1
v2 u2 l2
...
vm um lm
where n is the number of nodes, m the number of edges, s is the start (Kelvin's home) and t is the destination (Kelvin's school). The rest m lines are description of uni-directional roads: a line (v,u,l) meaning an directional edge of length l exists from v to u.
2 <= n <= 50
k <= 200
1 <= li <= 10000
There are at most one edges from a node v to u; there are no edge connecting any node to itself.
For each dataset in the input, one line should be output as specified below.
If the number of distinct paths from s to t is less than k, the string "None" should be printed (without quotes).
If the number of distinct paths from s to t is k or more, the node numbers visited in the k-th shortest path should be printed in the visited order, separated by a hyphen (minus sign). Note that s must be the first, and t must be the last in the printed line.
Here however, to distinguish different routes of same total length, we shall order all routes first by their length then by their lexicographical order. So the routes have an unique ordering and if there are a total number of at least k routes, there is always an unique solution.
5 20 10 1 5 1 2 1 1 3 2 1 4 1 1 5 3 2 1 1 2 3 1 2 4 2 2 5 2 3 1 1 3 2 2 3 4 1 3 5 1 4 1 1 4 2 1 4 3 1 4 5 2 5 1 1 5 2 1 5 3 1 5 4 1 4 6 1 1 4 2 4 2 1 3 2 1 2 1 1 4 3 2 3 1 3 4 1 3 3 5 1 3 1 2 1 2 3 1 1 3 1
1-2-4-3-5 1-2-3-4 None
In the case of the first dataset, there are 16 paths from the node 1 to 5. They are ordered as follows (The number in parentheses is the length of the path).
1 (3) 1-2-3-5
2 (3) 1-2-5
3 (3) 1-3-5
4 (3) 1-4-3-5
5 (3) 1-4-5
6 (3) 1-5
7 (4) 1-4-2-3-5
8 (4) 1-4-2-5
9 (5) 1-2-3-4-5
10 (5) 1-2-4-3-5
11 (5) 1-2-4-5
12 (5) 1-3-4-5
13 (6) 1-3-2-5
14 (6) 1-3-4-2-5
15 (6) 1-4-3-2-5
16 (8) 1-3-2-4-5
Migrated from old NTUJ.
Regional Japan 2006
| No. | Testdata Range | Score |
|---|