問題文

$N$ 頂点 $M$ 辺の重み付き有向グラフ $G$ があります。 $G$ の頂点には $1, 2, \\ldots, N$、辺には $1, 2, \\ldots, M$ と番号が振られています。 辺 $i$ は頂点 $u_i$ から頂点 $v_i$ へ張られており、辺の重みは $w_i$ です。 あなたは、$G$ 上で次のようなゲームをします。

初めに、所持金 $W$ 円を持って頂点 $S$ 上に立つ。その後、以下の操作を $K$ 回行う:

• 自分の今いる頂点から出ている辺を $1$ つ選んで、その辺が接続する頂点に移動する。
• このとき、選んだ辺の重みを $w$ とすると、$w$ が正ならば $w$ 円得る。逆に $w$ が負ならば $|w|$ 円失う。また、所持金が負となることはない。すなわち、元の所持金を $t$ 円とすると、移動後の所持金は $\\mathrm{max}(t+w, 0)$ 円である。

同じ辺を何度通ってもよく、通るたびに所持金が変化します。 $K$ 回の操作を完了する前に、移動が不可能になる頂点に訪れては行けません。 また、ゲーム終了時はどの頂点に立っていても構いません。

このとき、ゲーム終了時の所持金は最大でいくらにできるかを求め、出力してください。 ただし、どのように操作を行っても $K$ 回の操作を完了できない場合は、$\-1$ を出力してください。

制約

• $2 \\leq N \\leq 200$
• $0 \\leq M \\leq N (N-1)$
• $0 \\leq W \\leq 10^{16}$
• $1 \\leq S \\leq N$
• $1 \\leq K \\leq 10^9$
• $1 \\leq u_i, v_i \\leq N (1 \\leq i \\leq M)$
• $\-10^7 \\leq w_i \\leq 10^7 (1 \\leq i \\leq M)$
• $u_i \\neq v_i (1 \\leq i \\leq M)$
• $i \\neq j$ ならば $(u_i, v_i) \\neq (u_j, v_j)$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $W$ $S$ $K$ $u_1$ $v_1$ $w_1$ $:$ $u_M$ $v_M$ $w_M$

出力

$K$ 回の操作を完了できる場合には、ゲーム終了時の所持金の最大値を出力せよ。 どのように操作を行っても完了できない場合は、$\-1$ を出力せよ。

入力例 1

5 6 0 1 5
1 2 1
2 3 2
3 4 1
4 1 -1
3 1 -4
2 5 7

出力例 1

8

頂点を $1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 1 \\rightarrow 2 \\rightarrow 5$ と移動すれば、所持金は $8$ 円となります。

入力例 2

5 6 10 1 4
1 2 1
1 3 3
2 4 6
5 4 0
3 5 2
2 5 1

出力例 2

-1

どのように操作を行っても $4$ 回の操作を完了することはできません。したがって $\-1$ を出力します。

入力例 3

2 2 0 2 1000000000
1 2 100000
2 1 100000

出力例 3

100000000000000