Trọng tải

Đất nước Anpha có $n$ thành phố được đánh số từ $1$ đến $n$ và $m$ con đường hai chiều, mỗi con đường nối hai thành phố với nhau. Con đường thứ $i$ nối thành phố $u_i$ với thành phố $v_i$ và trọng tải cho phép được lưu thông tối đa là $w_i$ (gồm cả khối lượng của xe và khối lượng hàng hóa).

Beta là tài xế lái xe cho công ty chuyên cung cấp vật liệu xây dựng có trụ sở tại thành phố $X$ muốn chở một chuyến hàng đến thành phố $Y$.

Yêu cầu: Tìm khối lượng lớn nhất có thể mà vẫn có đường đi từ $X$ đến $Y$ đảm bảo đúng quy định về trọng tải.

Nói cách khác, một xe có khối lượng $K$ đi được trên con đường thứ $i$ khi và chỉ khi $K\le w_i$; cần tìm $K$ lớn nhất sao cho có một đường đi từ $X$ đến $Y$ mà mọi con đường trên đó đều cho xe đi qua. Có thể có nhiều con đường nối cùng một cặp thành phố, và có thể có con đường có $u_i=v_i$.

Dữ liệu vào

• Dòng đầu tiên chứa $4$ số nguyên dương $n,m,X,Y$ ($2\le n\le {10}^4$; $1\le m\le {10}^5$; $1\le X,Y\le n$; $X\ne Y$).
• Dòng thứ $i$ trong $m$ dòng tiếp theo chứa $3$ số nguyên $u_i,v_i,w_i$ ($1\le u_i,v_i\le n$; $0\le w_i\le {10}^9$).

Dữ liệu ra

In ra một số nguyên duy nhất là khối lượng lớn nhất tìm được. Nếu không có tuyến đường từ $X$ đến $Y$ thì ghi kết quả là $0$.

Ràng buộc

• $2\le n\le {10}^4$; $1\le m\le {10}^5$.
• $1\le X,Y\le n$; $X\ne Y$.
• $1\le u_i,v_i\le n$; $0\le w_i\le {10}^9$.
• Có $20\%$ số test tương ứng với $20\%$ số điểm của bài với $w_i=w_j$ với mọi $i,j\in [1..m]$.
• Có $40\%$ số test tương ứng với $40\%$ số điểm của bài với $w_i\le {10}^2$ với $1\le i\le m$.
• Có $40\%$ số test tương ứng với $40\%$ số điểm của bài không có thêm ràng buộc gì.

Ví dụ