Bạn cùng các bạn của mình đến một khu trượt tuyết để chơi trượt tuyết. Tại khu trượt tuyết, các điểm trung gian được thiết lập ở các độ cao khác nhau. Có tổng cộng $N$ điểm trung gian, được đánh số từ $1$ đến $N$ theo thứ tự độ cao giảm dần. Nghĩa là, điểm cao nhất là điểm $1$, và điểm thấp nhất là điểm $N$.

Hiện tại, bạn đang ở điểm $S$ cùng với các bạn của mình. Các bạn của bạn đã hẹn nhau sẽ tự do trượt tuyết, sau đó sẽ tập hợp lại tại điểm $T$ khi kết thúc.

Khu trượt tuyết có $M$ đường trượt. Mỗi đường trượt dẫn từ điểm $a_i$ đến điểm $b_i$, và nếu đi vào đường trượt này, bạn có thể trượt tuyết trong thời gian $t_i$. Các đường trượt luôn dẫn theo hướng độ cao giảm dần. Nghĩa là, chúng thỏa mãn $a_i < b_i$.

Ngoài ra, tại mỗi đường trượt đều có một cáp treo (ski lift). Cáp treo đi theo hướng ngược lại với đường trượt, tức là hướng độ cao tăng dần. Nghĩa là, nếu đi cáp treo, bạn có thể di chuyển từ điểm $b_i$ về điểm $a_i$. Bạn có thể đi cáp treo tối đa $K$ lần.

Bạn muốn đi đến điểm $T$ chỉ bằng cách sử dụng các đường trượt và cáp treo, đồng thời tối đa hóa tổng thời gian trượt tuyết. Thời gian đi cáp treo không được tính vào thời gian trượt tuyết. Cho biết thông tin về các đường trượt, hãy tính xem bạn có thể trượt tuyết trong tối đa bao lâu.

Dữ liệu vào

Dòng đầu tiên chứa năm số nguyên $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$).

Trong $M$ dòng tiếp theo, mỗi dòng chứa thông tin của một đường trượt gồm ba số nguyên $a_i, b_i, t_i$ ($1 \le a_i < b_i \le N$, $1 \le t_i \le 10^9$).

Có tối đa một đường trượt nối giữa hai điểm khác nhau bất kỳ.

Dữ liệu ra

In ra một số nguyên duy nhất là thời gian trượt tuyết tối đa có thể đạt được.

Nếu không có cách nào di chuyển đến điểm $T$ bằng cách sử dụng các đường trượt và cáp treo, hãy in ra $-1$.

Ví dụ

Dữ liệu vào 1

3 2 1 1 3
1 2 10
2 3 5

Dữ liệu ra 1

25

Dữ liệu vào 2

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

Dữ liệu ra 2

30

Dữ liệu vào 3

3 2 1 3 1
1 2 10
2 3 5

Dữ liệu ra 3

-1

Dữ liệu vào 4

3 2 2 3 1
1 2 10
2 3 5

Dữ liệu ra 4

0