JOI-kun sống trong một thành phố có \(N\) nhà ga, đánh số từ \(1\) đến \(N\). Có \(M\) tuyến đường sắt, đánh số từ \(1\) đến \(M\). Tuyến thứ \(i\) nối hai chiều giữa ga \(A_i\) và ga \(B_i\), với giá vé \(C_i\) yên.

JOI-kun sống gần ga \(S\) và đi học tại trường trung học IOI gần ga \(T\). Cậu dự định mua một vé tháng nối hai ga này. Khi mua vé tháng, cậu phải chọn một đường đi có tổng giá vé nhỏ nhất từ \(S\) đến \(T\). Với vé tháng đó, cậu có thể đi trên bất kỳ tuyến đường sắt nào thuộc đường đi đã chọn, theo bất kỳ chiều nào, mà không phải trả thêm tiền.

JOI-kun thường đến các hiệu sách gần ga \(U\) và ga \(V\). Vì vậy, cậu muốn chọn đường đi cho vé tháng sao cho chi phí đi từ \(U\) đến \(V\) nhỏ nhất.

Khi đi từ \(U\) đến \(V\), trước hết cậu chọn một đường đi giữa hai ga. Với mỗi tuyến đường sắt thứ \(i\) trên đường đi này, cậu phải trả:

• \(0\) yên nếu tuyến đó thuộc đường đi đã chọn khi mua vé tháng.
• \(C_i\) yên nếu tuyến đó không thuộc đường đi đã chọn khi mua vé tháng.

Chi phí đi từ \(U\) đến \(V\) là tổng các khoản tiền trên. Hãy tính chi phí nhỏ nhất có thể đạt được khi JOI-kun lựa chọn đường đi cho vé tháng một cách thích hợp.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N,M\), cách nhau bởi dấu cách, lần lượt là số nhà ga và số tuyến đường sắt.
• Dòng thứ hai chứa hai số nguyên \(S,T\), là hai ga mà vé tháng nối với nhau.
• Dòng thứ ba chứa hai số nguyên \(U,V\), là hai ga mà JOI-kun muốn giảm thiểu chi phí đi lại.
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa ba số nguyên \(A_i,B_i,C_i\), cách nhau bởi dấu cách. Tuyến thứ \(i\) nối hai chiều giữa \(A_i\) và \(B_i\), có giá vé \(C_i\) yên.

Dữ liệu ra

Ghi một dòng chứa chi phí nhỏ nhất để đi từ \(U\) đến \(V\), khi đường đi cho vé tháng được chọn một cách thích hợp.

Ràng buộc

• \(2\le N\le100\,000\).
• \(1\le M\le200\,000\).
• \(1\le S,T,U,V\le N\).
• \(S\ne T\).
• \(U\ne V\).
• \(S\ne U\) hoặc \(T\ne V\).
• Có thể đi từ bất kỳ ga nào đến bất kỳ ga nào khác bằng đường sắt.
• \(1\le A_i<B_i\le N\) với \(1\le i\le M\).
• Với mọi \(1\le i<j\le M\), có \(A_i\ne A_j\) hoặc \(B_i\ne B_j\); tức là không có hai tuyến nối cùng một cặp ga.
• \(1\le C_i\le10^9\) với \(1\le i\le M\).

Phân nhóm

1. (16 điểm) \(S=U\).
2. (15 điểm) Có duy nhất một đường đi có tổng giá vé nhỏ nhất từ \(S\) đến \(T\).
3. (24 điểm) \(N\le300\).
4. (45 điểm) Không có ràng buộc bổ sung.

Ví dụ

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

2

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

3000000000

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

15

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

0

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

19

Nguồn

JOI 2017/2018, vòng chung kết, bài Commuter Pass. Đề do Japanese Committee for the International Olympiad in Informatics công bố. Đề gốc tiếng Anh. Bản dịch tiếng Việt theo CC BY-SA 4.0.