You have come to a ski resort with your friends. In the ski resort, intermediate points are installed at certain altitudes. There are $N$ intermediate points in total, numbered from $1$ to $N$ in decreasing order of altitude. That is, the highest point is point $1$, and the lowest point is point $N$.

Currently, you are at point $S$ with your friends. Your friends agreed to gather at point $T$ after skiing freely.

There are $M$ slopes in the ski resort. Each slope goes from point $a_i$ to point $b_i$, and entering this slope allows you to ski for $t_i$ time. Slopes always go in the direction of decreasing altitude. That is, they satisfy $a_i < b_i$.

Also, there is a ski lift for each slope. The ski lift goes in the opposite direction of the slope, i.e., in the direction of increasing altitude. That is, if you take the ski lift, you can move from point $b_i$ to point $a_i$. You can ride the ski lift at most $K$ times.

You want to reach point $T$ using only the ski slopes and lifts, while maximizing the total time spent skiing. The time spent riding the lift is not included in the skiing time. Given the information of the slopes, find the maximum time you can ski.

Input

The first line contains five integers $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$).

The next $M$ lines contain the information of each slope as three integers $a_i, b_i, t_i$ ($1 \le a_i < b_i \le N$, $1 \le t_i \le 10^9$).

There is at most one slope connecting any two distinct points.

Output

Print a single integer representing the maximum time you can ski.

If it is impossible to reach point $T$ no matter how you choose the slopes and lifts, print -1 instead.

Examples

Input 1

3 2 1 1 3
1 2 10
2 3 5

Output 1

25

Input 2

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

Output 2

30

Input 3

3 2 1 3 1
1 2 10
2 3 5

Output 3

-1

Input 4

3 2 2 3 1
1 2 10
2 3 5

Output 4

0