Một hệ thống giao thông gồm \(n\) thành phố được đánh số từ 1 đến \(n\). Hệ thống giao thông có \(m\) đoạn đường hai chiều nối giữa các thành phố (giữa hai thành phố bất kỳ luôn có đường đi). Mỗi đoạn đường có một tải trọng tối đa là \(z\), cho biết các xe với tải trọng không lớn hơn \(z\) mới lưu thông được trên con đường đó.

Yêu cầu: Cho trước tải trọng của các đoạn đường trong hệ thống giao thông. Hãy tìm một hành trình từ thành phố \(s\) đến thành phố \(t\) sao cho tải trọng cho phép của xe lưu thông trên hành trình đó là lớn nhất có thể.

Dữ liệu vào:

+ Dòng thứ nhất ghi 4 số nguyên \(n,\ m,\ s,\ t\) \((2 \leq n \leq 10^{3};1 \leq m \leq 10^{4};\ 1 \leq s,\ t \leq n;\ s
eq t)\)

+ Tiếp theo là \(m\) dòng, mỗi dòng ghi 3 số nguyên \(x,\ y,\ z\) với ý nghĩa có đoạn đường giữa thành phố \(x\) và thành phố \(y\) với tải trọng tối đa cho phép là \(z\) \((1 \leq z \leq 10^{4})\)

Các số trên một dòng ghi cách nhau ít nhất 1 ký tự trắng

Kết quả: Ghi số nguyên là tải trọng lớn nhất cần tìm.

Ví dụ:

Ràng buộc: 50% số test tương ứng với 50% số điểm của bài có \(2 \leq n \leq 100\)