你和朋友们一起去滑雪场滑雪。滑雪场在不同的海拔高度设有中途点。一共有 $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