Tại đất nước VNOI, có ~n~ thành phố được kết nối với nhau bằng một hệ thống giao thông gồm ~m~ con đường hai chiều có trọng số. Hệ thống này luôn đảm bảo tính liên thông, nghĩa là giữa hai thành phố bất kì luôn có ít nhất một đường đi giữa chúng.

Ở mỗi thành phố luôn có một trạm xăng với vô hạn xăng, nhưng trên đường đi giữa hai thành phố kề nhau lại không có trạm xăng nào, do đó khi dừng chân tại một thành phố, bạn có thể đổ đầy bình xăng của mình. Biết với mỗi lần đi giữa hai thành phố kề nhau, bạn bị mất một lượng xăng là trọng số của con đường đó; hãy tính dung tích nhỏ nhất của bình xăng của xe bạn, mà đảm bảo rằng bạn không bao giờ bị hết xăng khi đang di chuyển trên đường đi giữa hai thành phố bất kì.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ (~2 \le n \le 2 \cdot 10^5~, ~1 \le m \le 4 \cdot 10^5~) — thể hiện số thành phố và số con đường trực tiếp giữa hai thành phố.

Trong ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i \ v_i \ d_i~ thể hiện rằng có đường đi trực tiếp giữa ~u_i~ và ~v_i~ với trọng số ~d_i~ (~1 \le u_i,v_i \le n~, ~0 \le d_i \le 10^5)~.

Output

In ra một số nguyên duy nhất là đáp án của bài toán.

Scoring

Sample Input 1

3 2
1 2 5
1 3 10

Sample Output 1

10

Sample Input 2

3 3
1 2 5
1 3 10
2 3 5

Sample Output 2

5

Notes

• Ví dụ thứ nhất: xe của bạn cần có ít nhất ~10~ đơn vị xăng, để đảm bảo có thể di chuyển từ ~1 \rightarrow 3~ và ~2 \rightarrow 3~ mà không bị hết xăng.

• Ví dụ thứ hai: xe của bạn chỉ cần chứa ít nhất ~5~ đơn vị xăng, do mọi đường đi tốt nhất giữa các cặp đỉnh chỉ cần đi qua các cạnh có trọng số ~5~.