你和朋友們一起來到滑雪場滑雪。滑雪場在不同的高度設有中繼點。中繼點共有 $N$ 個，並依高度遞減的順序編號為 $1$ 到 $N$。也就是說，最高的地點是 $1$ 號地點，最低的地點是 $N$ 號地點。

目前你和朋友們在 $S$ 號地點。你的朋友們約好各自自由地滑雪，結束後在 $T$ 號地點集合。

滑雪場有 $M$ 條滑雪道。每條滑雪道從 $a_i$ 號地點連向 $b_i$ 號地點，進入該滑雪道可以滑行 $t_i$ 的時間。滑雪道總是朝著高度降低的方向延伸。也就是說，滿足 $a_i < b_i$。

此外，每條滑雪道都設有滑雪纜車。滑雪纜車的方向與滑雪道相反，朝著高度增加的方向延伸。也就是說，搭乘滑雪纜車可以從 $b_i$ 號地點移動到 $a_i$ 號地點。滑雪纜車最多可以搭乘 $K$ 次。

你希望僅使用滑雪道和纜車前往 $T$ 號地點，並使滑行時間最大化。搭乘纜車的時間不計入滑行時間。給定滑雪道的資訊，求最多可以滑行多少時間。

輸入格式

第一行給定五個整數 $N, M, K, S, T$（$1 \le N, M \le 10^5$，$0 \le K \le 10$，$1 \le S, T \le N$）。

接下來 $M$ 行，每行給定一條滑雪道的資訊，包含三個整數 $a_i, b_i, t_i$（$1 \le a_i < b_i \le N$，$1 \le t_i \le 10^9$）。

連接任意兩個不同地點的滑雪道最多只有一條。

輸出格式

輸出一個整數，表示最多可以滑行的時間。

如果無論如何選擇滑雪道和纜車都無法到達 $T$ 號地點，則輸出 -1。

範例

輸入 1

3 2 1 1 3
1 2 10
2 3 5

輸出 1

25

輸入 2

3 3 1 1 3
1 2 10
2 3 5
1 3 1

輸出 2

30

輸入 3

3 2 1 3 1
1 2 10
2 3 5

輸出 3

-1

輸入 4

3 2 2 3 1
1 2 10
2 3 5

輸出 4

0