Cho đồ thị vô hướng liên thông có ~n~ đỉnh và ~m~ cạnh.

Yêu cầu: Hãy cho biết độ dài đường đi ngắn nhất từ đỉnh ~s~ bắt buộc đi qua đỉnh ~v~ rồi đến đỉnh ~t~. Biết rằng độ dài của một đường đi là tổng trọng số của các cạnh trên đường đi đó sao cho trọng số của một cạnh được cộng vào đúng một lần.

Dữ liệu vào:

• Dòng đầu tiên ghi 2 số nguyên dương ~n,m~ ~(1 ≤ n ≤ 10^5; n ≤ m ≤ min⁡(10^5, n(n-1)/2)~.
• Dòng thứ hai ghi lần lượt 3 số ~s,t,v~ ~(1≤s,t,v≤n)~
• ~m~ dòng tiếp theo, mỗi dòng ghi 3 số nguyên lần lượt là ~x,y,c~ ~(1 ≤ x,y ≤ n; 1 ≤ c ≤ 10^9)~ cho biết cạnh ~x,y~ có trọng số ~c~.

Dữ liệu ra:

• Một số nguyên duy nhất cho biết kết quả của bài toán.

Ví dụ:

Input

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

Output

6 

Ràng buộc:

• Có 20% số test có ~𝑠 = 𝑡~
• Có 60% số test khác có kết quả là độ dài của đường đi đơn.
• Có 20% số test còn lại không ràng buộc gì thêm.