Giấy quý báu

Một quốc gia có $N$ nhà máy và $N$ sân bay. Cần chọn $N$ cặp (nhà máy, sân bay) sao cho mỗi nhà máy được ghép với đúng một sân bay và mỗi sân bay được ghép với đúng một nhà máy.

Vì lý do pháp lý, không phải cặp (sân bay, nhà máy) nào cũng có thể xây dựng đường. Bạn được cho $M$ cặp khả dĩ; với mỗi cặp $(u,v)$ ta biết $d$ — số ngày cần để xây dựng đường nối sân bay $u$ với nhà máy $v$.

Nếu khởi công xây dựng tất cả các đường được chọn cùng một lúc, thời gian hoàn tất toàn bộ chính là $d$ lớn nhất trong các đường đã chọn. Hãy chọn $N$ cặp sao cho thời gian hoàn tất là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $M$.
• $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$, $d$ — mô tả một đường khả dĩ giữa sân bay $u$ và nhà máy $v$ với chi phí $d$ ngày.

Dữ liệu ra

• Nếu không có cách ghép cặp hợp lệ, in ra $-1$.
• Ngược lại, in ra giá trị nhỏ nhất của thời gian hoàn tất (bằng $d$ lớn nhất trong các đường đã chọn).

Ràng buộc

• $1\le N\le {10}^4$
• $1\le M\le {10}^5$
• $1\le u,v\le N$
• $1\le d\le {10}^9$
• Có thể có nhiều đường khác nhau giữa cùng một cặp $(u,v)$.

Ví dụ