3137：Enjoyable Commutation

The input consists of multiple datasets, each in the following format.

n	m	k	a	b
x1	y1	d1
x2	y2	d2
…
xm	ym	dm

Every input item in a dataset is a non-negative integer. Two or more input items in a line are separated by a space.

n is the number of nodes in the graph. You can assume the inequality 2 ≤ n ≤ 50. m is the number of (directed) edges. a is the start node, and b is the goal node. They are between 1 and n, inclusive. You are required to find the k-th shortest path from a to b. You can assume 1 ≤ k ≤ 200 and a ≠ b.

The i-th edge is from the node x_i to y_i with the length d_i (1 ≤ i ≤ m). Both x_i and y_i are between 1 and n, inclusive. d_i is between 1 and 10000, inclusive. You can directly go from x_i to y_i, but not from y_i to x_i unless an edge from y_i to x_i is explicitly given. The edge connecting the same pair of nodes is unique, if any, that is, if i ≠ j, it is never the case that x_i equals x_j and y_i equals y_j. Edges are not connecting a node to itself, that is, x_i never equals y_i. Thus the inequality 0 ≤ m ≤ n(n − 1) holds.

Note that the given graph may be quite unrealistic as a road network. Both the cases m = 0 and m = n(n − 1) are included in the judges’ data.

The last dataset is followed by a line containing five zeros (separated by a space).

For each dataset in the input, one line should be output as specified below. An output line should not contain extra characters such as spaces.

If the number of distinct paths from a to b is less than k, the string None should be printed. Note that the first letter of None is in uppercase, while the other letters are in lowercase.

If the number of distinct paths from a to b 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 a must be the first, and i must be the last in the printed line.

In this problem the term shorter (thus shortest also) has a special meaning. A path P is defined to be shorter than Q, if and only if one of the following conditions holds.

1. The length of P is less than the length of Q. The length of a path is defined to be the sum of lengths of edges on the path.
2. The length of P is equal to the length of Q, and P’s sequence of node numbers comes earlier than Q’s in the dictionary order. Let’s specify the latter condition more precisely. Denote P’s sequence of node numbers by p₁, p₂, …, p_s, and Q’s by q₁, q₂, …, q_t. p₁ = q₁ = a and p_s = q_t = b should be observed. The sequence P comes earlier than Q in the dictionary order, if for some r (1 ≤ r ≤ s and r ≤ t), p₁ = q₁, …, p_{r − 1} = q_{r − 1}, and p_r < q_r (p_r is numerically smaller than q_r).

A path visiting the same node twice or more is not allowed.