ami càng ngày càng gần với việc thu thâp 6 vũ khí, và kẻ thù cũng ngày càng mạnh hơn. ami sẽ phải đối mặt với ma sa xét cuom1999. Để dàng chiến thắng, ami cần vượt qua mê cung tử thần và dành lấy vũ khí áo choàng chống lửa.

Mê cung tử thần có \(n\) căn phòng và \(m\) cổng không gian. Để các bạn dễ hình dung, các căn phòng được đánh số từ \(1\) đến \(n\), các cổng không gian được đánh số từ \(1\) đến \(m\). Mỗi cây cầu không gian nối \(2\) phòng khác nhau theo một chiều, và có một con số ám ảnh là \(w_{i}\).

Tuy nhiên, chỉ việc vượt qua mê cung vẫn là chưa đủ. ami cần vượt qua mê cung với độ ám ảnh ít nhất. ami sẽ bắt đầu ở căn phòng \(a\) và đích đến là căn phòng \(b\). ami chỉ có thể di chuyển giữa \(2\) phòng nếu giữa chúng tồn tại một cồng không gian. Nếu ami dùng các cổng không gian \(w_{1}, w_{2}, w_{3}, \ldots, w_{k}\) thì độ ám ảnh sẽ là \(w_{1}\) OR \(w_{2}\) OR \(\ldots\) OR \(w_{k}\). ami có phép dịch chuyển, nên cậu đã đến cồng \(b\) một cách nhanh chóng. ami đố các bạn rằng ami đã đến đó với độ ám ảnh bao nhiêu?

Input

• Dòng đầu chứa \(4\) số nguyên dương \(n, m, a, b\) \((2 \leq n \leq 10^{5}, 1 \leq m \leq 4 \times 10^{5}, 1 \leq a, b \leq n, a \neq b)\).
• Mỗi dòng trong \(m\) dòng tiếp theo \(u, v, w\) \((1 \leq u, v \leq n, 0 \leq w \leq 10^{9})\) - đại diện cho một cổng không gian một chiều từ \(u\) đến \(v\) với độ ám ảnh \(w\).

Ouput

• In ra một dòng là độ ám ảnh nhỏ nhất.
• Nếu không có cách di chuyển từ \(a\) đến \(b\) thì in ra \(-1\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(w \leq 1\) (các con đường có giá trị \(0\) hoặc \(1\)).
• Subtask \(2\) (\(10\%\) số điểm): \(n \leq 10, m \leq 15\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 1000, m \leq 4000, w \leq 1000\).
• Subtask \(4\) (\(60\%\) số điểm): Không có rằng buộc gì thêm.

Example

3 4 1 3
1 2 1
1 2 4
2 3 2
1 3 5

3

3 4 3 1
1 2 1
1 2 4
2 3 2
1 3 5

-1