Ngưu Lang là vị thần chăn trâu của Ngọc Hoàng Thượng đế, vì say mê một tiên nữ phụ trách việc dệt vải tên là Chức Nữ nên bỏ bễ việc chăn trâu, để trâu đi nghênh ngang vào điện Ngọc Hư. Chức Nữ cũng vì mê tiếng tiêu của Ngưu Lang nên trễ nải việc dệt vải. Ngọc Hoàng giận dữ, bắt cả hai phải ở cách xa nhau, người đầu sông Ngân, kẻ cuối sông. Mỗi năm họ chỉ được gặp nhau một lần vào rằm tháng 7 âm lịch. Đó là trong truyền thuyết, còn trong thời đại 4.0 này câu chuyện có phần hơi khác.

Theo đó, thiên đình có \(n\) khu được đánh số từ \(1\) đến \(n\), Ngưu Lang ở khu \(1\) còn Chức Nữ ở khu \(n\). Cầu Ô Thước không phải chỉ có \(1\) mà là có \(m\), cầu thứ \(i\) nối khu \(x_i\) với khu \(y_i\) và được xây dựng xong vào ngày thứ \(t_i\). Vậy là cầu được xây chứ không phải do chim quạ và chim khách xếp thành nữa. Do đó họ cũng không nhất thiết phải gặp nhau vào rằm tháng 7, mà sẽ gặp vào một thời điểm sớm nhất trong năm sao cho tại thời điểm đó, những cây cầu đã xây xong đảm bảo tồn tại một đường đi từ \(1\) đến \(n\).

Ngưu Lang vốn lập trình giỏi, nhưng do vướng vào yêu đương nên trình độ giảm sút đi nhiều. Anh ấy muốn nhờ bạn tính giúp thời điểm sớm nhất mà họ có thể gặp nhau, biết rằng chắc chắn tồn tại thời điểm như thế.

Input

• Dòng đầu chứa hai số nguyên dương: \(n\) \(m\)
• Dòng thứ \(i\) trong số \(m\) dòng tiếp theo chứa: \(x_i\) \(y_i\) \(t_i\)

Output

• Ghi thời điểm sớm nhất họ gặp nhau

Scoring

• \(1 \leq n \leq 10^5\), \(1 \leq m \leq 10^5\), \(1 \leq t \leq 10^9\)

• Có \(50\%\) số test với \(n, m, t \leq 100\)

• Subtast \(1\): Có thể xét hết các thời điểm rồi kiểm tra

• Subtast \(2\): Nạp lần lượt các cạnh vào cây khung cho đến khi 1 và n thuộc cùng một thành phần liên thông.
  Cũng có thể chặt nhị phân thời điểm, với mỗi thời điểm ta nạp hết các cạnh xây dựng trước thời điểm đó vào đồ thị rồi dùng BFS/DFS để kiểm tra tính liên thông của 1 và n

Example

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

4