Hệ thống giao thông công cộng nơi Vinh ở gồm ~N~ ga xe buýt, các ga được đánh số thứ tự từ ~1~ đến ~N~. Có ~M~ tuyến đường hai chiều nối giữa các cặp ga. Tuyến đường thứ ~i (i = 1,2,..,M)~ nối trực tiếp cặp ga ~A_i~ và ~B_i~, chi phí di chuyển trên tuyến đường này là ~C_i~. Mỗi cặp ga chỉ có nhiều nhất một tuyến đường nối chúng. Nhà Vinh ở gần ga ~S~ và trường học ở gần ga ~T~. Hằng ngày đến trường Vinh đi bộ đến ga ~S~ rồi lên xe buýt để đi đến ga ~T~. Khi đến ga ~T~, Vinh sẽ đi bộ đến trường. Vinh đã mua vé tháng cho đường đi từ ga ~S~ đến ga ~T~ với tổng chi phí trên các tuyến đường thuộc đường đi đó là nhỏ nhất. Sáng chủ nhật hàng tuần, Vinh có sở thích đến thư viện để đọc sách. Nhà Vinh cũng ở gần ga ~U~ và thư viện ở gần ga ~V~. Để đến thư viện, Vinh đi bộ đến ga ~U~ rồi đi xe buýt để đến ga ~V~, sau đó đi bộ đến thư viện. Để khuyến khích học sinh đến thư viện đọc sách, Ban quản lý ga xe buýt sẽ không thu phí khi đi trên các tuyến đường mà học sinh đó đã mua vé tháng. Nghĩa là, khi Vinh đi từ ga ~U~ đến ga ~V~, nếu Vinh đi trên các tuyến đường thuộc đường đi từ ga ~S~ đến ga ~T~ mà Vinh đã mua vé tháng thì sẽ không mất phí, các tuyến đường không thuộc sẽ bị mất phí.

Yêu cầu: Bạn hãy tính xem, Vinh có thể chọn đường đi nào để đi từ ga ~S~ đến ga ~T~ (tất nhiên đường đi từ ~S~ đến ~T~ có tổng chi phí ít nhất) mà khi đi từ ga ~U~ đến ga ~V~ mất tổng chi phí là nhỏ nhất.

Dữ liệu gồm:

• Dòng đầu ghi hai số nguyên dương ~N~ và ~M~ số ga xe buýt và số tuyến đường nối trực tiếp giữa hai ga (~2 ≤N≤10^5; 1≤M≤2.10^5)~.
• Dòng thứ hai ghi hai số ~S~ và ~T (1≤S,T≤N, S≠T)~.
• Dòng thứ ba ghi hai số ~U~ và ~V (1≤U,V≤N, U≠V)~.
• Dòng thứ ~i~ trong ~M~ dòng cuối, ghi ba số nguyên dương ~A_i,B_i,C_i~ mô tả tuyến đường nối trực tiếp ga ~A_i~ và ga ~B_i~ với chi phí là ~C_i (1<A_i≠B_i≤N; 1 ≤C_i≤10^9)~.</li>

Kết quả:

• Tổng chi phí ít nhất mà Vinh có thể đi từ ga ~U~ đến ga ~V~.

Ví dụ:

Input

6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

Out

2

Giải thích

• Vinh sẽ mua vé theo đường đi: 1 → 2 → 3 → 5 → 6 (có tổng chi phí nhỏ nhất).
• Vinh đi đến thư viện theo tuyến đường: 1 → 2 → 3 →5 → 4, chỉ mất chi phí tuyến đường 5→4 là 2.

Giới hạn:

• Có 15% số test ứng với ~S~ = ~U~;
• Có 15% số test ứng với trường hợp chỉ có ~1~ đường đi duy nhất từ ~S~ đến ~T~ có tổng chi phí nhỏ nhất;
• Có 25% số test ứng với ~N ≤300~;
• Có 45% số test còn lại không có ràng buộc gì thêm;