Cạnh đầu trong cây khung nhỏ nhất

Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh. Mỗi cạnh có một trọng số nguyên không âm. Không có hai cạnh nào nối cùng một cặp đỉnh.

Xét cạnh đầu tiên trong danh sách đầu vào, gọi là $c_1$, nối hai đỉnh $u$ và $v$. Ta muốn biết: có thể đặt trọng số mới $e$ cho cạnh $c_1$ lớn nhất bằng bao nhiêu sao cho cạnh $c_1$ vẫn có thể thuộc một cây khung nhỏ nhất nào đó của đồ thị?

Cụ thể, hãy tìm giá trị nguyên $e$ lớn nhất với $0\le e\le {10}^9$ thỏa mãn: nếu thay trọng số của $c_1$ bằng $e$ (giữ nguyên các cạnh khác) thì tồn tại ít nhất một cây khung nhỏ nhất của đồ thị có chứa $c_1$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ ($2\le n\le {10}^5$, $n-1\le m\le {10}^6$).
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a$, $b$, $w$ mô tả một cạnh nối đỉnh $a$ với đỉnh $b$ có trọng số $w$ ($1\le a,b\le n$, $a\ne b$, $0\le w\le {10}^9$).

Đảm bảo không có hai cạnh trùng cặp đỉnh và đồ thị liên thông.

Dữ liệu ra

Một số nguyên duy nhất: giá trị $e$ lớn nhất tìm được.

Ràng buộc

• $2\le n\le {10}^5$
• $n-1\le m\le {10}^6$
• $1\le a,b\le n$, $a\ne b$
• $0\le w\le {10}^9$

Ví dụ