Giải bài trực tuyến

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 (N<= 50000 ,M ≤ 100000)
- 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 (u,v<=N;l<=2 tỷ)

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

Example

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

Output: 
5