Đi xe buýt

Xe buýt là một phương tiện giao thông phổ biến tại thành phố mà Alice sinh sống bởi tính tiện dụng và giá cả hợp lý của nó. Thành phố có $n$ bến xe buýt được đánh số từ $1$ tới $n$ và có $m$ tuyến xe buýt hai chiều, mỗi tuyến đang được điều hành bởi một trong hai công ty vận tải $A$ hoặc $B$. Cụ thể, tuyến thứ $i$ $(1\le i\le m)$ di chuyển giữa hai bến $u_i$ và $v_i$ với giá vé do công ty quản lý quy định là $w_i$.

Lưu ý là giữa hai bến có thể có nhiều hơn một tuyến xe buýt.

Hai công ty $A$ và $B$ đều có chính sách giảm giá vé cho những ai thường xuyên đi bằng xe buýt. Cụ thể, mỗi ngày công ty $A$ sẽ chỉ thu số tiền bằng với giá vé lớn nhất trong tất cả các tuyến được điều hành bởi công ty $A$ mà khách hàng đã đi trong ngày. Để cạnh tranh, công ty $B$ cũng có chính sách tương tự: khách hàng sẽ chỉ phải trả số tiền bằng giá vé lớn nhất trong tất cả các tuyến thuộc công ty $B$ mà người đó đã đi trong ngày.

Nhà Alice ở gần bến xe buýt $s$ và nơi làm của Alice ở gần bến xe buýt $t$ nên hàng ngày Alice đều phải đi lại giữa hai bến này thông qua các tuyến xe buýt.

Yêu cầu: Bạn hãy giúp Alice xác định số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo việc đi từ bến xe buýt $s$ đến bến xe buýt $t$.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên dương $n$, $m$, $s$ và $t$ $(n,m\le 50000;s,t\le n;s\ne t)$;
• Dòng thứ $i$ $(1\le i\le m)$ trong $m$ dòng tiếp theo chứa bốn số nguyên dương $c_i,u_i,v_i,w_i$ $(u_i,v_i\le n;u_i\ne v_i;w_i\le {10}^9)$ mô tả tuyến xe buýt thứ $i$, trong đó $c_i=1$ nếu tuyến này được điều hành bởi công ty $A$ hoặc $c_i=2$ nếu tuyến này được điều hành bởi công ty $B$.

Các số trên cùng một dòng cách nhau bởi dấu cách. Dữ liệu đảm bảo luôn tồn tại cách đi lại giữa hai bến xe buýt $s$ và $t$ thông qua $m$ tuyến xe.

Dữ liệu ra

In ra một số nguyên duy nhất là số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo được việc đi từ bến xe buýt $s$ đến bến xe buýt $t$ cho Alice.

Ràng buộc

• $n,m\le 50000$; $1\le s,t\le n$; $s\ne t$;
• $c_i\in \{1,2\}$; $1\le u_i,v_i\le n$; $u_i\ne v_i$; $1\le w_i\le {10}^9$;
• Luôn tồn tại cách đi từ $s$ đến $t$.

Subtasks

• Subtask 1 ($20\%$ số test, $20\%$ số điểm): tất cả $m$ tuyến xe buýt đều được điều hành bởi công ty $A$;
• Subtask 2 ($30\%$ số test, $30\%$ số điểm): $n,m\le 5000$;
• Subtask 3 ($20\%$ số test, $20\%$ số điểm): tồn tại cách đi xe buýt tối ưu trong đó Alice chỉ sử dụng tối đa một tuyến xe của công ty $B$;
• Subtask 4 ($30\%$ số test, $30\%$ số điểm): không có điều kiện gì thêm.

Ví dụ