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

Một đơn vị vận chuyển có $n$ trung tâm trung chuyển được đánh số từ $1$ đến $n$. Giữa hai trung tâm trung chuyển được nối bởi 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 giữa hai trung tâm $a_i$ và $b_i$ và có khoảng cách là $c_i$ $(i=1...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

• Dòng thứ nhất ghi $4$ số nguyên dương $n,m,s,t$ $(1\le s,t\le n\le {10}^5;1\le m\le {10}^5;s\ne t)$.
• Dòng thứ $i$ trong $m$ dòng tiếp theo ghi ba số nguyên $a_i,b_i,c_i$ $(1\le ai,bi\le n,a_i\ne b_i;0\le c_i\le {10}^9)$.

Dữ liệu ra

• Một số nguyên dương duy nhất 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$.

Input 1

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

Output 1

8