Vào năm 2050, thành phố Tam Kỳ đã xây dựng tổng cộng \(N\) trạm tàu điện ngầm và \(M\) tuyến đường ray hai chiều nối chúng với nhau. Tuyến đường ray thứ \(i\) \((1\leq i\leq M)\) nối hai trạm \(A_i\) và \(B_i\) với giá vé là \(C_i\).

Nhà của Dương ở gần trạm \(S\), và hàng ngày cậu sẽ di chuyển đến trường NBK gần trạm \(T\) bằng các tuyến tàu điện ngầm. Dương được phép mua một tấm voucher đặt biệt: cậu chỉ cần chọn bất kỳ một đường đi rẻ nhất từ \(S\) đến \(T\), và sau khi áp dụng tấm voucher đặt biệt này, cậu có thể đi qua toàn bộ các tuyến đường ray nằm trên đường đi được chọn đó mà không cần tốn một đồng nào để mua vé. Hiển nhiên, lúc đó thì cậu có thể thoải mái di chuyển từ trạm \(S\) đến trạm \(T\) với chi phí bằng \(0\).

(Một đường đi rẻ nhất từ \(S\) đến \(T\) là một chuỗi các đường ray bắt đầu từ trạm \(S\) và kết thúc ở trạm \(T\) sao cho tổng giá vé của chúng là nhỏ nhất có thể)

Ngoài hai trạm \(S\) và \(T\), Dương cũng rất hay di chuyển giữa hai trạm \(U\) và \(V\) (trạm \(U\) là tiệm quà Tanbobo còn trạm \(V\) là nhà idol Chou Dang của cậu). Dù tấm voucher đặc biệt chỉ áp dụng trên một đường đi rẻ nhất từ \(S\) đến \(T\), cậu vẫn muốn tính toán xem nên chọn ra đường đi nào để đồng thời cũng cực tiểu hóa được giá tiền để di chuyển từ trạm \(U\) đến trạm \(V\).

Các bạn hãy lập trình tính toán giúp Dương nhé!

Input

Dòng đầu chứa hai số nguyên dương \(N\) và \(M\).

Dòng tiếp theo chứa hai số nguyên dương \(S\) và \(T\). \((1\leq S\ne T\leq N)\)

Dòng tiếp theo chứa hai số nguyên dương \(U\) và \(V\). \((1\leq U\ne V\leq N)\)

Dòng thứ \(i\) \((1\leq i\leq M)\) trong \(M\) dòng tiếp theo chứa ba số nguyên dương \(A_i\), \(B_i\), và \(C_i\).

Output

Một số nguyên duy nhất là chi phí nhỏ nhất để di chuyển từ trạm \(U\) đến trạm \(V\) sau khi áp dụng tấm voucher đặc biệt trên một tuyến đường từ \(S\) đến \(T\).

Ví dụ

Sample input 1

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

Sample output 1

2

Giải thích

Dương có thể áp dụng voucher đặc biệt với đường đi: \(1\rightarrow 2\rightarrow 3\rightarrow 5\rightarrow 6\).

Sau đó, cậu có thể di chuyển từ \(U\) đến \(V\) (\(1\) đến \(4\)) thông qua đường đi \(1\rightarrow 2\rightarrow 3\rightarrow 5\rightarrow 4\) với chi phí \(0+0+0+2=2\).

Sample input 2

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

Sample output 2

3000000000

Sample input 3

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

Sample output 3

15

Sample input 4

5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10

Sample output 4

0

Sample input 5

10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16

Sample output 5

19

Ràng buộc

Trong tất cả các test:

• \(2\leq N\leq 10^5\)
• \(1\leq M\leq 2\cdot 10^5\)
• Không tồn tại \(i\ne j\) mà \(A_i=A_j\) và \(B_i=B_j\).
• \(1\leq C_i\leq 10^9\).

Subtasks

• Subtask 1 (16 điểm): \(S=U\).
• Subtask 2 (15 điểm): Giữa \(S\) và \(T\) tồn tại đúng một đường đi rẻ nhất.
• Subtask 3 (24 điểm): \(N\leq 300\).
• Subtask 3 (45 điểm): Không có ràng buộc gì thêm.