Công ty có một hệ thống mạng nội bộ gồm \(n\) thiết bị và \(m\) dây nối giữa các cặp thiết bị. Các thiết bị được đánh số từ \(1\) đến \(n\). Các dây nối được đánh số từ \(1\) đến \(m\). Dây nối thứ \(i (1≤i≤m)\) kết nối hai thiết bị \(X_i,Y_i\) và có độ trễ là \(W_i\). Đảm bảo không có hai dây nối nào kết nối cùng một cặp thiết bị và luôn tồn tại ít nhất một đường truyền giữa hai cặp đỉnh bất kì.

Gọi đường truyền giữa hai thiết bị \(X\) và \(Y\) là dãy các thiết bị \((X=x_1,x_2,…,x_k=Y)\) sao cho với mọi \(i (1≤i<k)\) thì có dây nối giữa hai đỉnh \(x_i\) và \(x_{i+1}\), và độ trễ của đường truyền trên là tổng độ trễ của các dây nối giữa các \(x_i\) và \(x_{i+1}\).

Gọi độ trễ giữa hai thiết bị \(X\) và \(Y\) là độ trễ bé nhất của đường truyền bất kì giữa hai thiết bị \(X\) và \(Y\).

Sắp tới bạn được giao nhiệm vụ cải tạo một trong những đường truyền có độ trễ bé nhất giữa hai thiết bị \(S\) và \(T\) (chọn đường truyền nhanh nhất để tiết kiệm chi phí).

Nếu bạn chọn cải tạo đường truyền \((S=y_1,y_2,…,y_k=T)\) thì với mọi \(i (1≤i<k)\), dây nối giữa các cặp thiết bị \(y_i\) và \(y_{i+1}\) sẽ được giảm độ trễ xuống bằng \(0\) (các dây nối thuộc đường truyền được cải tạo hầu như không còn độ trễ). Vì lí do riêng mà bạn muốn sau lần cải tạo này độ trễ giữa hai thiết bị \(U\) và \(V\) là bé nhất có thể.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên \(n,m (2≤n≤10^5,1≤m≤2×10^5)\) là số thiết bị và số dây nối;
• Dòng thứ hai chứa hai số nguyên \(S,T (1≤S,T≤n,S≠T)\);
• Dòng thứ ba chứa hai số nguyên \(U,V (1≤U,V≤n,U≠V)\);
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(X_i,Y_i,W_i\) tương ứng với một dây nối giữa hai thiết bị \(X_i\) và \(Y_i\), dây nối thứ \(i\) có độ trễ là \(W_i (1≤X_i<Y_i≤n,1≤W_i≤10^9)\).

Kết quả:

• Một dòng duy nhất chứa một số nguyên, là độ trễ nhỏ nhất có thể giữa hai thiết bị \(U\) và \(V\) sau khi cải tạo các kết nối.

Ví dụ:

Input

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

Output

2

Giải thích:

• Lựa chọn cải tiến đường truyền: \((1,2,3,5,6)\);

• Sau đó đường truyền có độ trễ nhỏ nhất giữa hai thiết bị \(1\) và \(4\) là \((1,2,3,5,4)\). Trong đó độ trễ của dây nối giữa hai thiết bị \(5\) và \(4\) là \(2\), độ trễ của các dây nối còn lại trên đường truyền này đều là \(0\).

Ràng buộc:

• Subtask 1: (16% số điểm) \(S=U\);
• Subtask 2: (15% số điểm) có duy nhất một đường truyền có độ trễ nhỏ nhất giữa hai thiết bị \(S\) và \(T\);
• Subtask 3: (24% số điểm) \(n≤300\);
• Subtask 4: (45% số điểm) không có ràng buộc gì thêm.