Thành phố bạn Lam sống có ~n~ nút giao thông được đánh số từ ~1~ đến ~n~. Việc đi lại giữa các nút giao thông được thực hiện qua các tuyến xe bus. Có tất cả ~m~ tuyến, tuyến thứ ~i~ cho phép di chuyển hai chiều từ nút giao thông ~a_i~ đến ~b_i~ ~(a_i \ne b_i)~ và có tiền vé một lượt đi là ~c_i~. Các tuyến xe bus được xây dựng để đảm bảo mọi cặp nút giao thông trong thành phố đều có thể liên thông với nhau thông qua một số tuyến xe trực tiếp hoặc gián tiếp.

Nhà của Lam ở nút giao thông ~s~ còn trường học thì ở nút giao thông ~t~. Để tiết kiệm chi phí, Lam đã tìm một con đường thông qua một số tuyến xe bus để di chuyển từ nhà tới trường với tổng tiền vé nhỏ nhất. Để thuận tiện hơn, Lam đã mua vé năm cho tất cả các tuyến trên con đường đó. Các tuyến đã mua vé năm thì trong năm đó có thể đi lại mà không cần trả phí nữa. Ngoài việc thường xuyên đi lại từ nhà tới trường, Lam còn thường đến thư viện ở nút giao thông ~u~, đến trung tâm Anh ngữ ở nút giao thông ~v~. Do đó, Lam muốn lựa chọn con đường từ nhà tới trường sao cho chi phí di chuyển từ ~u~ tới ~v~ là nhỏ nhất.

Yêu cầu: Tìm chi phí nhỏ nhất để Lam di chuyển từ ~u~ tới ~v~ sau khi đã mua vé năm cho con đường từ ~s~ tới ~t~ theo như mô tả trên.

Input

• Dòng đầu chứa ~2~ số nguyên dương ~n~ và ~m~ ~(n \le 10^5; m \le 2 \cdot 10^5)~.

• Dòng thứ hai chứa ~2~ số nguyên dương ~s~ và ~t~ ~(s,t \le n)~.

• Dòng thứ ba chứa ~2~ số nguyên dương ~u~ và ~v~ ~(u,v \le n)~.

• Dòng thứ ~i~ trong ~m~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên dương ~a_i, b_i, c_i~ mô tả tuyến xe bus thứ ~i~ ~(a_i,b_i \le n; c_i \le 10^9; 1 \le i \le m)~.

Các số trên một dòng cách nhau bởi một dấu cách.

Output

Ghi ra một số nguyên duy nhất là kết quả tìm được.

Scoring

Sample Input 1

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

Sample Output 1

5

Sample Input 2

9 10
1 6
3 8
1 2 3
2 4 2
2 3 3
4 5 1
3 5 2
5 6 3
2 7 4
8 2 3
9 3 1
8 9 1

Sample Output 2

2

Notes

• Trong ví dụ thứ nhất, đường đi từ ~s~ đến ~t~: ~(1) \rightarrow (2) \rightarrow (4) \rightarrow (5) \rightarrow (6)~ có chi phí nhỏ nhất là ~9~. Đường đi từ ~u~ đến ~v~: ~(3) \rightarrow (5) \rightarrow (4) \rightarrow (2) \rightarrow (8)~ có chi phí nhỏ nhất là ~5~ do chỉ phải trả thêm tiền vé cho tuyến ~(3) \rightarrow (5)~ và ~(2) \rightarrow (8)~.

• Trong ví dụ thứ hai, đường đi từ ~s~ đến ~t~: ~(1) \rightarrow (2) \rightarrow (4) \rightarrow (5) \rightarrow (6)~ có chi phí nhỏ nhất là ~9~. Đường đi từ ~u~ đến ~v~: ~(3) \rightarrow (9) \rightarrow (8)~ có chi phí nhỏ nhất là ~2~ do chỉ phải trả tiền vé cho tuyến ~(3) \rightarrow (9)~ và ~(9) \rightarrow (8)~.