Trong một chiến dịch quy mô lớn của Liên minh Không gian, bạn được giao nhiệm vụ thiết lập hệ thống truyền tín hiệu điều khiển từ Trạm Trung Tâm được đánh số thứ tự là ~1~ đến toàn bộ các trạm vệ tinh còn lại (từ ~2~ đến ~n~). Các tín hiệu sẽ được truyền qua các vệ tinh trung gian, thông qua những tuyến truyền có sẵn.

Mỗi tuyến truyền là một kết nối một chiều từ vệ tinh ~u~ đến vệ tinh ~v~, với một mức nhiễu tín hiệu là ~w~. Nếu tín hiệu đi qua tuyến này, nó sẽ chịu ảnh hưởng bởi độ nhiễu ~w~, có thể làm sai lệch mệnh lệnh điều khiển.

Tuy nhiên, không phải tuyến nào cũng cần được sử dụng. Bạn có thể tắt bớt một số tuyến truyền, với điều kiện là vẫn phải đảm bảo mọi trạm vệ tinh đều có thể nhận tín hiệu khởi nguồn từ Trạm Trung Tâm.

Mục tiêu của bạn là thiết kế lại hệ thống sao cho:

• Mỗi trạm vẫn nhận được tín hiệu từ trạm trung tâm.
• Trong toàn bộ hệ thống được giữ lại, tuyến truyền nào có mức nhiễu cao nhất thì mức nhiễu đó phải nhỏ nhất có thể. Nói cách khác, hãy giảm tối đa ảnh hưởng của nhiễu tồi tệ nhất có thể xảy ra trong bất kỳ tuyến truyền nào được giữ lại.

Input

• Dòng đầu: Chứa hai số nguyên dương ~n~ và ~m~ lần lượt là số trạm vệ tinh và số tuyến truyền tín hiệu.
• ~m~ dòng sau: Mỗi dòng gồm ba số nguyên dương ~u,v~ và ~w~ thể hiện tuyến truyền tín hiệu một chiều từ trạm ~u~ đến trạm ~v~ có độ nhiễu là ~w~. ~(w \leq 10^9)~

Output

• Gồm một số nguyên duy nhất là đáp án của nhiệm vụ đã giao hoặc in ~-1~ nếu không có đáp án thoả mãn.

Sample Input

4 5
1 2 4
2 3 8
1 3 6
3 4 2
2 4 10

Sample Output

6

Explanation

• Loại bỏ tuyến truyền tín hiệu ~2 → 3~ có trọng số là ~8~ và tuyến truyền tín hiệu ~2 → 4~ có trọng số là ~10~.
  • 
• Sau khi hoàn thành nhiệm vụ thiết lập hệ thống truyền tín hiệu điều khiển từ Trạm Trung Tâm:
  • 

Constraints

• ~40\%~ số test đầu tiên tương ứng với ~40\%~ số điểm có ~n \leq 100, m \leq 10^3~.
• ~20\%~ số test tiếp thep tương ứng với ~20\%~ số điểm có ~n \leq 10^3, m \leq 10^4~.
• ~20\%~ số test tiếp theo tương ứng với ~20\%~ số điểm có ~n \leq 10^4, m \leq 10^5~.
• ~20\%~ số test cuối cùng tương ứng với ~20\%~ số điểm có ~n \leq 10^5, m \leq 5\times10^5~.