Cho bản đồ giao thông gồm N thành phố (đánh số từ 1 đến N) và M con đường một chiều nối giữa các thành phố, mỗi con đường có độ dài w (km). Một tài xế cần đi từ thành phố S đến thành phố T. Hãy tìm độ dài quãng đường ngắn nhất từ S đến T. Nếu không có đường đi, in ra -1.

Đầu vào

• Dòng đầu chứa bốn số nguyên N (1 ≤ N ≤ 10^5), M (1 ≤ M ≤ 10^5), S, T.
• M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w (1 ≤ u, v ≤ N, 0 ≤ w ≤ 10^9) — đường từ u đến v dài w km.

Đầu ra

Một số nguyên là độ dài đường đi ngắn nhất, hoặc -1.

Ví dụ

Input:
5 6 1 5
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1

Output:
6