Có một câu chuyện trên ngọn đồi đón gió, kể về Q và C hai người bạn thanh mai trúc mã của nhau.
Họ đã cùng nhau trải qua nhiều kỷ niệm đẹp trên ngọn đồi của mình, khiến cho C không thể quên được. Rồi đến một ngày C quyết định nỗ lực để chiếm được trái tim của Q. Nhưng Q là một cô nàng nghịch ngợm và lắm trò nên chàng C của chúng ta cũng chẳng thể chinh phục một cách dễ dàng.

Q cho C một thử thách là cõng Q đi qua hết cả ~N~ ngọn đồi đón gió. Các ngọn đồi này được nối với nhau bởi M con đường mòn một chiều (giữa hai ngọn đồi chỉ có không quá một con đường như thế), mỗi con đường nối giữa hai ngọn đồi ~u,v~ thì để đi qua, cần có yêu cầu về thể lực riêng là ~w~. Do đó, yêu cầu về thể lực của C khi đi qua một chặng gồm nhiều con đường mòn sẽ là max các giá trị ~w~ trên mỗi con đường mòn riêng. Nói một cách ngắn gọn, Q muốn được C cõng đi thăm hết cả ~N~ ngọn đồi này trên những con đường mòn thơ mộng, một ngọn đồi có thể qua bao nhiêu lần tùy thích nhưng quan trọng là phải đi đủ hết; đồng thời, xuất phát ở đâu thì phải kết thúc ở đó. Đây là một thử thách rất lớn cho C, vì rõ ràng có thể có khả năng không đi được, hoặc là đòi hỏi về thể lực lại quá cao.

Cảm động cho điều này, một thiên sứ tình yêu đã cho C một khả năng rất hay là: có thể chọn ra vài con đường mòn và đổi chiều của chúng (ban đầu đi từ ~u \to v~ thì lúc sau sẽ thành đi từ ~v \to u~), nhưng vẫn giữ nguyên giá trị ~w.~ Mỗi con đường chỉ được chọn và đổi không quá một lần và tất nhiên C có thể cũng không cần đổi lần nào. Với phép màu đó, bạn hãy tính thử xem yêu cầu về thể lực nhỏ nhất mà C cần có là bao nhiêu, để C biết mà còn luyện tập cho đạt. Tất nhiên, đôi khi phép màu cũng không giúp ích được, nghĩa là cho dù có đổi chiều thế nào thì cũng không qua được hết ~N~ ngọn đồi, điều này có thể khiến C trầm cảm một thời gian.

Input

• Dòng đầu tiên gồm hai số nguyên ~N, M~ với ~1 \le N \le 10^5~ và ~1 \le M \le 2 \cdot 10^5~.

• Trong ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u, v, w~ với ~1 \le u, v \le N~ và ~1 \le w \le 10^9~, mô tả con đường thứ ~i~ từ ~u~ đến ~v~ cũng như đòi hỏi về thể lực ~w~ trên con đường đó.

Output

Nếu không có cách nào đổi chiều mà đi được qua hết ~N~ ngọn đồi thì in ra ~-1~. Nếu có cách đi được và hơn nữa, có thể điều chỉnh hướng của các con đường để cho yêu cầu về thể lực càng nhỏ càng tốt thì in ra giá trị nhỏ nhất đó.

Sample Input 1

3 3
1 2 1
2 3 2
3 1 3

Sample Output 1

3

Sample Input 2

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

Sample Output 2

3

Sample Input 3

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

Sample Output 3

-1

Sample Input 4

5 8
1 2 4
2 3 5
3 4 6
4 5 3
3 5 1
1 3 7
1 4 9
2 5 8

Sample Output 4

7

Giải thích:

• Trong VD1, C có thể cõng Q đi qua các ngọn đồi theo thứ tự ~1 \to 2 \to 3 \to 1~ và thể lực cần thiết là ~3~ (ở đây C không cần đổi chiều con đường nào cả).

• Trong VD2, C lúc đầu không thể đi được nhưng có thể đổi hướng cạnh ~1 \to 3~ thành ~3 \to 1~ thì đi được qua hết các đỉnh với yêu cầu thể lực là ~3~.

• Trong VD3, C có thể theo hướng ~1 \to 2 \to 3 \to 4~ qua được ~4~ ngọn đồi nhưng lại không có cách nào quay về vị trí xuất phát là ~1.~

• Trong VD4, ta có thể đổi hướng đường ~3 \to 5~ thành ~5 \to 3~, đổi ~1 \to 3~ thành ~3 \to 1~ thì sẽ có cách đi là: ~1 \to 2 \to 3 \to 4 \to 5 \to 3 \to 1~, xuất phát từ ~1~ và quay được về ~1~, yêu cầu thể lực chỉ có ~7~, sẽ có những cách đi khác dùng cạnh ~(1,4)~ hay ~(2,5)~ nhưng cần các năng lực lớn hơn không cần thiết.

Theo bạn, còn có thử thách nào khó hơn như vậy nữa không?