Đất nước HYPER có ~N~ thành phố khác nhau. Để kết nối các thành phố bằng đường bộ, Chính phủ đã đề ra ~M~ phương án xây dựng những con đường một chiều giữa các thành phố.

Với phương án thứ ~i~ (~1 \le i \le M~) biểu diễn dưới dạng ~(u, v, w)~. Khi đó bạn chỉ có thể:

• Xây con đường một chiều nối từ ~u~ đến ~v~ với chi phí là ~w~.

• Hoặc xây con đường một chiều nối từ ~v~ đến ~u~ với chi phí là ~w~.

• Hoặc không sử dụng phương án này.

Yêu cầu: Hãy tìm cách sử dụng các phương án xây dựng sao cho từ một thành phố có đường đi đến các thành phố còn lại, đồng thời chi phí lớn nhất để xây dựng một con đường nối giữa hai thành phố là nhỏ nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N, M~ (~N \le 10^5, M \le 2 \cdot 10^5~);

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~u, v, w~ (~u, v \le N, w \le 10^9~) mô tả phương án thứ ~i~.

Dữ liệu vào đảm bảo không có phương án nào xây đường đi từ một thành phố đến chính nó.

Output

Nếu không có cách sử dụng các phương án thỏa mãn thì in ra số ~-1~, ngược lại in ra chi phí lớn nhất để xây dựng một con đường nối giữa hai thành phố là nhỏ nhất.

Scoring

Sample Input 1

4 5
1 2 1
1 4 2
2 3 3
2 4 4
3 4 3

Sample Output 1

3

Sample Input 2

4 4
1 2 1
2 3 2
3 4 3
4 2 4

Sample Output 2

-1

Notes

Ví dụ 1:

• Phương án 1: Chọn xây ~5~ đường nối các thành phố là ~1 \to 2~ (1), ~2 \to 3~ (3), ~2 \to 4~ (4), ~3 \to 4~ (3), ~4 \to 1~ (2). Chi phí lớn nhất để xây một con đường là ~4~.

• Phương án 2: Chọn xây ~4~ đường nối các thành phố là ~1 \to 2~ (1), ~2 \to 3~ (3), ~3 \to 4~ (3), ~4 \to 1~ (2). Chi phí lớn nhất để xây một con đường là ~3~.

Chi phí nhỏ nhất tìm được là: ~3~.