Given a directed weighted network $G = (V, E)$, a weight function $w: E \to \mathbb{Z}^+$ (where the weight $w(e)$ of any edge $e$ is a positive integer), and two nodes $s, t \in V$. Select an edge set $S \subseteq E$ such that there is no path from $s$ to $t$ in $G' = (V, E - S)$. Let $\mathcal{S}$ be the set of all such edge sets $S$. Output the edge weight sums $w(S)$ of the $k$ smallest edge sets in $\mathcal{S}$, in non-decreasing order. Here, $w(S) = \sum_{e \in S} w(e)$.

Input

The first line contains 5 integers $n, m, s, t, k$, where $n$ and $m$ represent $|V|$ and $|E|$ (the number of nodes and edges, respectively). Nodes in the graph are represented by integers from $1$ to $n$.

The next $m$ lines each contain 3 integers $x, y, z$, representing a directed edge from $x$ to $y$ with weight $z$.

Output

If $|\mathcal{S}| < k$, first output $|\mathcal{S}|$ lines, each containing an integer representing the $w(S)$ of the first $|\mathcal{S}|$ edge sets; then output a single line containing $-1$.

If $|\mathcal{S}| \geq k$, output $k$ lines, each representing the $w(S)$ of one of the first $k$ edge sets.

In both cases, the values of $w(S)$ must be output in non-decreasing order.

Examples

Input 1

3 3 1 3 100
1 2 3
2 3 4
1 3 5

Output 1

8
9
12
-1

Input 2

5 8 1 5 10
1 2 45176
1 3 41088
1 4 32001
2 5 48931
3 5 39291
4 5 28970
2 3 48131
4 2 49795

Output 2

116468
117192
118265
120223
145438
147235
149193
157556
158280
161311

Input 3

See kcut/kcut.in and kcut/kcut.ans in the contestant directory.

Constraints