Ngày nay, việc mua sắm trực tuyến trở nên phổ biến. Chúng ta có thể chọn đặt mua những sản phẩm thông qua các kênh bán hàng trực tuyến. Sau đó đơn vị vận chuyển sẽ nhận kiện hàng và giao đến tận nhà.

Một đơn vị vận chuyển có ~n~ trung tâm trung chuyển đánh số từ ~1~ đến ~n~. Giữa hai trung tâm trung chuyển được nối với nhau tối đa một tuyến đường hai chiều. Có tất cả ~m~ tuyến đường, tuyến đường thứ ~i~ nối hai trung tâm ~a_i~ và ~b_i~ có khoảng cách là ~c_i~ ~(i = 1\dots m)~.

Yêu cầu: Hãy xác định tổng khoảng cách ngắn nhất để vận chuyển một kiện hàng từ trung tâm trung chuyển ~s~ đến trung tâm trung chuyển ~t~.

Dữ liệu vào

• Cho từ tệp văn bản VANCHUYEN.INP có dạng:
  • Dòng thứ nhất ghi bốn số nguyên ~n, m, s, t~ ~(1 \le s, t \le n \le 10^5, 1 \le m \le 10^5, s \neq t)~.
  • Dòng thứ ~i~ trong ~m~ dòng tiếp theo ghi ba số nguyên dương ~a_i, b_i, c_i~ ~(1 \le a_i, b_i \le n, a_i \neq b_i, 0 < c_i \le 10^9)~.

Các số trên cùng một dòng được cách nhau một dấu cách.

Kết quả

• Ghi ra tệp văn bản VANCHUYEN.OUT gồm một dòng ghi số nguyên dương là tổng khoảng cách ngắn nhất để vận chuyển kiện hàng từ trung tâm trung chuyển ~s~ đến trung tâm trung chuyển ~t~.

Ràng buộc

• Có ~80\%~ số test ứng với ~80\%~ số điểm có giá trị ~n \le 10^3~.
• Có ~20\%~ số test ứng với ~20\%~ số điểm có giá trị ~n \le 10^5~.

Ví dụ

Dữ liệu vào

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

Kết quả

10