Đất nước ABC có tất cả ~n~ thôn được đánh số từ ~1~ đến ~n~ và có ~m~ con đường hai chiều nối các thôn với nhau. Sau đợt mưa lũ vừa qua, hầu hết các tuyến đường đều bị sạt, lở rất nguy hiểm. Tuyến đường thứ ~i~ nối hai thôn ~u_i~ và ~v_i~ có mức độ nguy hiểm là ~w_i~ (~i = 1, 2, \dots, n~). Sau kỳ nghỉ hè tại nhà ở thôn ~s~, Nam chuẩn bị đến trường ở thôn ~t~ để bắt đầu năm học mới.

Yêu cầu: Hãy giúp Nam tìm một hành trình từ nhà đến trường sao cho độ nguy hiểm của hành trình là nhỏ nhất có thể. Độ nguy hiểm của một hành trình được định nghĩa là độ nguy hiểm lớn nhất trong số các tuyến đường đi qua. Tuy nhiên, điều đáng chú ý ở đây là: Nam được thần Đèn cấp cho tối đa ~k~ lệnh, mỗi lệnh được phép di chuyển tức thì giữa hai thôn có đường nối với nhau và lúc này độ nguy hiểm được coi bằng ~0~.

Input

• Dòng thứ nhất gồm năm số nguyên ~n, m, k, s, t~ (~n, m \le 10^5; k \le 20; 1 \le s, t \le n~);

• Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ba số nguyên ~u_i, v_i, w_i~ (~1 \le u_i, v_i \le n; w_i \le 10^9~).

Các số ghi trên cùng một dòng được phân cách nhau bởi một dấu cách.

Output

Ghi ra một số nguyên là độ nguy hiểm nhỏ nhất của hành trình tìm được; nếu không có đường đi thì in ra ~-1~.

Scoring

Sample Input 1

5 6 1 1 5
1 2 100
1 3 4
3 4 5
4 2 3
5 4 2
2 5 4

Sample Output 1

3

Notes

Dùng lệnh của thần Đèn từ thôn ~1 \rightarrow 2~ nên độ nguy hiểm là ~\max(3, 2) = 3~.