Đang trong mùa cao điểm du lịch tại vịnh Lạ Hong. Vịnh Lạ Hong có \(n\) hòn đảo được đánh số từ \(1\) đến \(n\). Tuy nhiên, theo đài dự báo thời tiết thì sắp tới sẽ có bão trên vịnh, vì thế ban quản lý vịnh quyết định sẽ xây các cây cầu tạm thời để phục vụ cho việc sơ tán của người dân. Theo kế hoạch, ban quản lý sẽ cho xây \(M\) cây cầu, cây cầu thứ \(j\) nối giữa hai hòn đảo \(u_j\) và \(v_j\) (\(1\leq u_j, v_j\leq n\), \(u_j \ne v_j\)) và thời gian để đi qua cây cầu từ đảo \(u_j\) đến đảo \(v_j\) là \(w_j\) (đơn vị thời gian).

Ban quản lý tiến hành tập trung du khách từ \(n-1\) đảo trên về đảo \(1\) để tiến hành công tác sơ tán người dân về nơi an toàn. Tại thời điểm \(0\), các du khách bắt đầu di chuyển từ các hòn đảo. Biết rằng các du khách trên cùng một hòn đảo thì sẽ đi cùng một lúc và đến nơi cùng một thời điểm.

Hãy xác định thời điểm sớm nhất mà tất cả các vị khách đều tập trung tại hòn đảo \(1\)?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(m\) (\(n \leq 10^5\), \(m\leq 2\times 10^5\));
• \(m\) dòn tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(u_j\), \(v_j\) và \(w_j\) (\(1 \leq u_j, v_j \leq 10^6\), \(u_j \ne v_j\), \(1 \leq w_j \leq 10^6\)) - mô tả một cây cầu.

Output

• Thời điểm gần nhất mà tất cả các du khách đều tập trung về hòn đảo \(1\), tính theo đơn vị thời gian.

Example

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

7

Nguồn: Ôn tập Olympic năm 2024