Find the k-th shortest path between two fixed vertices in an undirected graph.

Input

First line contains number of vertices n (1 ≤ n ≤ 100) and edges m (1 ≤ m ≤ 4000) in the graph, and the number of the path k (1 ≤ k ≤ 500). Next lines describe the graph edges - triple (u, v, w) describes the edge connecting the vertices u and v of weight w. The last line contains numbers of two vertices s and t, between which the path must be found.

There can be no multiple edges in a graph; there can be no loops. All weights are positive and do not exceed 10000. It is guaranteed that the k-th path exists.

Output

In the first line print two numbers - the desired weight of the path and the number of vertices in it. In the next line print the path itself - a sequence of vertex numbers.