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 xi to yi with the length di (1 ≤ i ≤ m). Both xi and yi are between 1 and n, inclusive. di is between 1 and 10000, inclusive. You can directly go from xi to yi, but not from yi to xi unless an edge from yi to xi 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 xi equals xj and yi equals yj. Edges are not connecting a node to itself, that is, xi never equals yi. 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).