Sắp xếp lỗ sâu

• $N$ con bò ở sai vị trí (hoán vị $p$). Có $M$ lỗ sâu, mỗi lỗ nối hai vị trí với độ rộng $w$. Hai con bò ở hai đầu lỗ sâu có thể hoán đổi vị trí. Tìm giá trị lớn nhất $W$ sao cho chỉ dùng lỗ sâu có độ rộng $\ge W$ cũng đủ để đưa mọi bò về đúng vị trí. In $-1$ nếu đã đúng vị trí.

Dữ liệu vào

• Dòng đầu: $N$ và $M$.
• Dòng thứ hai: hoán vị $p_1,\dots ,p_N$.
• $M$ dòng tiếp: $a_i$, $b_i$, $w_i$.

Dữ liệu ra

• $W$ lớn nhất, hoặc $-1$.

Ràng buộc

• $1\le N,M\le {10}^5$
• $1\le w_i\le {10}^9$

Ví dụ