Yen algorithm

Input

The first line contains the number of vertices $n$ (1 \leq n \leq 100) and edges $m$ (1 \leq m \leq 4000) in the graph, and the number of the path $k$ (1 \leq k \leq 500).

The next $m$ lines describe the graph edges. Each line contains a triple (u, v, w), describing an edge connecting the vertices $u$ and $v$ of weight $w$.

The last line contains the 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.

Examples