Để động viên phong trào toàn dân tham gia các hoạt động thể thao giữ gìn sức khỏe, hằng năm báo Sức khỏe cộng đồng tổ chức một giải chạy phong trào. Có ~n~ điểm đăng ký và ~m~ con đường hai chiều, mỗi đường nối giữa 2 điểm đăng ký, tạo thành một mạng đường chạy (giữa hai điểm có thể có nhiều đường nối).

Người dự thi chọn một điểm bất kỳ để đăng ký, sau đó chạy theo các đường trong mạng sao cho:

• Mỗi đường không được chạy qua quá một lần.
• Kết thúc hành trình phải quay trở về đúng điểm đăng ký ban đầu.

Khi chạy hết đường thứ ~j~, người tham gia nhận được một thẻ chứng nhận ghi số nguyên ~c_j~. Sau khi hoàn thành vòng chạy, người tham gia được phát một túi hồng xiêm có số quả bằng ~\min(c_j)+\max(c_j)~, trong đó ~c_j~ là các số ghi trên những thẻ đã nhận được trong vòng chạy.

Yêu cầu

Hãy xác định số quả hồng xiêm nhiều nhất mà một người tham gia có thể nhận được.

Dữ liệu

• Dòng đầu chứa hai số nguyên ~n~ và ~m~ (~1 \le n, m \le 10^5~).
• Trong ~m~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên ~u_j, v_j, c_j~: có một đường hai chiều nối trực tiếp giữa ~u_j~ và ~v_j~, khi chạy qua đường này nhận được thẻ ghi ~c_j~.
• Giữa hai điểm có thể có nhiều đường nối.

Kết quả

In ra một số nguyên — số quả hồng xiêm lớn nhất có thể nhận được.

Ví dụ

Ví dụ 1

Input

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

Output

4

Giải thích

Ví dụ 1

Chọn vòng chạy: ~1 \rightarrow 2 \rightarrow 4 \rightarrow 1~.

Các thẻ nhận được có giá trị: ~2, 2, 2~ nên ~\min=2~, ~\max=2~, do đó số quả nhận được là ~2+2=4~ (lớn nhất).

Ràng buộc

• ~1 \le n, m \le 10^5~.
• Đồ thị vô hướng, có thể có đa cạnh (nhiều đường nối giữa cùng một cặp điểm).
• Mỗi đường chỉ được đi qua không quá một lần và phải quay về điểm xuất phát.