Trạm thu phí đắt nhất (Highest Paid Toll)

Nguồn: UVa Online Judge

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một đồ thị có hướng gồm $N$ địa điểm và $M$ con đường. Mỗi con đường $u\to v$ có phí sử dụng $c$.

Bạn cần đi từ $s$ đến $t$ với tổng phí của toàn bộ hành trình không vượt quá ngân sách $p$.

Trong tất cả các hành trình hợp lệ, hãy tìm mức phí lớn nhất của một con đường có thể xuất hiện trên hành trình.

Input

Dòng đầu chứa năm số nguyên $N,M,s,t,p$.

Trong $M$ dòng tiếp theo, mỗi dòng chứa $u,v,c$, mô tả một con đường một chiều từ $u$ đến $v$ có phí $c$.

Phiên bản Phước Hưng OJ chứa đúng một test case; số lượng test case $T$ của đề gốc đã được loại bỏ.

Output

In mức phí lớn nhất của một con đường có thể thuộc một hành trình từ $s$ đến $t$ có tổng phí không vượt quá $p$.

Nếu không tồn tại hành trình hợp lệ, in -1.

Subtask

Trong tất cả các Subtask: $1\le s,t,u,v\le N$; $u\ne v$; $1\le p\le10^6$; $0\le c\le10^5$.

• Subtask 1 — 20% — 0.75 giây: $2\le N\le100$; $1\le M\le500$.
• Subtask 2 — 30% — 1.50 giây: $2\le N\le2000$; $1\le M\le2\cdot10^4$.
• Subtask 3 — 50% — 3.00 giây: $2\le N\le10^4$; $1\le M\le10^5$.

Ví dụ

Input

5 6 1 5 10
1 2 7
2 5 4
1 3 6
3 5 3
1 4 5
4 5 4

Output

6

Giải thích

Đường $1\to3\to5$ có tổng phí $6+3=9\le10$ và chứa cạnh phí $6$. Đường qua cạnh phí $7$ có tổng $11$, vượt ngân sách. Vì vậy đáp án là $6$.