HIWAY2 - Hai đường đi (version 2)

Giới hạn

• Thời gian: 0.2s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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

---

• Người up: tienpro