Những con bò của Farmer John đã chán ngấy việc mỗi sáng ông đều yêu cầu chúng tự sắp xếp trước khi rời chuồng. Chúng vừa hoàn thành bằng tiến sĩ vật lý lượng tử và đã sẵn sàng tăng tốc mọi việc một chút.

Sáng nay, như thường lệ, \(N\) con bò của Farmer John (\(1\le N\le 10^5\)), được đánh số thuận tiện từ \(1\dots N\), đang rải rác tại \(N\) vị trí phân biệt trong chuồng, cũng được đánh số từ \(1\dots N\), sao cho bò \(i\) đang ở vị trí \(p_i\). Nhưng sáng nay còn có \(M\) hố giun (\(1\le M\le 10^5\)), được đánh số từ \(1\dots M\); hố giun \(i\) nối hai chiều vị trí \(a_i\) với vị trí \(b_i\) và có độ rộng \(w_i\) (\(1\le a_i,b_i\le N\), \(a_i\neq b_i\), \(1\le w_i\le 10^9\)).

Tại bất kỳ thời điểm nào, hai con bò nằm ở hai đầu đối diện của một hố giun có thể chọn đồng thời đổi chỗ cho nhau qua hố giun đó. Những con bò phải thực hiện các lần đổi chỗ như vậy cho đến khi bò \(i\) ở vị trí \(i\) với mọi \(1\le i\le N\).

Những con bò không muốn bị các hố giun ép bẹp. Hãy giúp chúng tối đa hóa độ rộng của hố giun hẹp nhất mà chúng buộc phải sử dụng để tự sắp xếp. Đề bài đảm bảo rằng những con bò có thể tự sắp xếp được.

Phân nhóm

• Các test từ \(3\) đến \(5\) thỏa mãn \(N,M\le 1000\).
• Các test từ \(6\) đến \(10\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp wormsort.in.

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).

Dòng thứ hai chứa \(N\) số nguyên \(p_1,p_2,\dots,p_N\). Đề bài đảm bảo \(p\) là một hoán vị của \(1\ldots N\).

Với mỗi \(i\) từ \(1\) đến \(M\), dòng thứ \(i+2\) chứa ba số nguyên \(a_i\), \(b_i\) và \(w_i\).

Dữ liệu ra

Ghi ra tệp wormsort.out một số nguyên: giá trị lớn nhất có thể của độ rộng nhỏ nhất trong số các hố giun mà một con bò phải chui ép qua trong quá trình sắp xếp. Nếu những con bò không cần dùng hố giun nào để tự sắp xếp, hãy in ra \(-1\).

Ví dụ

4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3

9

4 1
1 2 3 4
4 2 13

-1

Nguồn

• Kỳ thi: USACO 2020 January Contest, Silver
• Tên bài: Wormhole Sort
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=992
• Tác giả đề: Dhruv Rohatgi