Một mạng giao thông gồm N nút giao thông, và có ~M~ đường hai chiều nối một số cặp nút, thông tin về một đường gồm ba số nguyên dương ~u, v~ là tên hai nút đầu mút của đường, và ~l~ là độ dài đoạn đường đó. Biết rằng hai nút giao thông bất kì có không quá ~1~ đường hai chiều nhận chúng làm hai đầu mút.

Cho hai nút giao thông ~s~ và ~f~, hãy tìm hai đường đi nối giữa ~s~ với ~f~ sao cho hai trên hai đường không có cạnh nào được đi qua hai lần và tổng độ dài ~2~ đường đi là nhỏ nhất.

Input

• Dòng đầu ghi ~N, M , S , F~ ~\left(N \leq 50000;\text{ } M \leq 100000\right)~
• ~M~ dòng tiếp theo, mỗi dòng mô tả một đường gồm ba số nguyên dương ~u, v, l~ ~\left(u,v \leq N;\text{ } l \leq 2 \times 10^9\right)~

Output

Gồm ~1~ dòng duy nhất là tổng độ dài nhỏ nhất tìm được hoặc ghi ra ~-1~ nếu không có đường đi

Sample Input

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

Sample Output

5