Cho đồ thị có ~ n ~ đỉnh và ~ m ~ cạnh, các đỉnh được đánh số từ 1 đến ~ n ~. Trên mỗi cạnh được gán một số nguyên không âm là trọng số của cạnh đó. Trọng số của một đường đi được tính bằng phép toán ~ or ~, Nói cách khác, một đường đi qua các cạnh có trọng số lần lượt là ~ m_1, m_2, …, m_k ~ thì trọng số của đường đi này là ~ m_1 ~ ~ or ~ ~ m_2 ~ ~ or ~ … ~ m_k ~ Cho đồ thị và 2 đỉnh ~ s, t ~, hãy tìm đường đi có trọng số nhỏ nhất từ ~ s ~ đến ~ t ~, nếu không tìm được đường đi thì in ~ -1 ~.

Dữ liệu vào

• Dòng đầu tiên ghi 2 số nguyên ~ n, m ~ ~ 1 ≤ n ≤ 1000 ~; ~ 1 ≤ m ≤ 10000 ~
• ~ m ~ dòng tiếp theo, mỗi dòng ghi 3 số nguyên ~ u, v, c ~ ~ (1 ≤ u, v ≤ n) ~ cho biết ~ c ~ ~ (1 ≤ c < 1024) ~ là trọng số của cạnh ~ u, v ~
• Dòng cuối cùng ghi 2 số nguyên ~ s, t ~ ~ (1 ≤ s, t ≤ n; s ≠ t) ~

Kết quả

• Một số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Input 1

3 4
1 2 1
1 2 1000
2 3 3
1 3 100
1 3 

Output 1

3