Sơn và Vinh là hai người bạn thân thiết vì cùng chung sở thích là tham gia vào các trò chơi trí tuệ. Sơn mới nghĩ ra một trò chơi mới để thách đố Vinh. Trò chơi được mô tả như sau: Trên mặt phẳng Sơn vẽ một bản đồ giao thông gồm ~n~ nút. Các nút được đánh số từ ~1~ đến ~n~. Giữa các nút có ~m~ đoạn đường cho phép đi theo cả hai chiều. Trên mỗi đoạn đường có đặt một số quả chuối. Vinh được phép xuất phát từ một nút tuỳ ý đi theo các đoạn đường nối giữa các nút rồi quay trở lại nút xuất phát. Trong quá trình di chuyển không được phép di chuyển qua cùng một đoạn đường nhiều hơn một lần. Giả sử số lượng chuối trên các đoạn đường mà Vinh chọn để di chuyển qua là ~s_1, s_2, \ldots, s_k~. Khi đó số điểm mà Vinh đạt được theo cách đi này là ~\min{(s_1, s_2, \ldots, s_k)} + \max{(s_1, s_2, \ldots, s_k)}~.

Yêu cầu: Hãy giúp Vinh tìm cách đi đạt được nhiều điểm nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ theo thứ tự là số lượng nút và số lượng đoạn đường giữa các nút trên bản đồ;
• Dòng thứ ~i~ trong số ~m~ dòng tiếp theo chứa ba số nguyên ~u_i~, ~v_i~, ~w_i~ ~(1 \le u_i, v_i \le n; \; u_i \ne v_i; \; 0 \le w_i \le 10^9)~, trong đó ~u_i, v_i~ là chỉ số của ~2~ điểm được nối với nhau bởi đoạn đường thứ ~i~ và ~w_i~ là số lượng quả chuối có trên đoạn đường này, ~i = 1, 2, \ldots, m~. Chú ý là có thể có nhiều hơn một đoạn đường nối cùng một cặp nút.

Các số trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

Một số nguyên là điểm số lớn nhất có thể đạt được trong trò chơi. Hãy ghi ra ~0~, nếu trên bản đồ không có cách đi thoả mãn điều kiện đặt ra.

Giới hạn

• Có ~40\%~ số lượng test thoả mãn điều kiện: ~n \le 10, m \le 100~;
• Có thêm ~30\%~ số lượng test thoả mãn điều kiện: ~n, m \le 5\,000~;
• ~30\%~ số lượng test còn lại thoả mãn điều kiện: ~n, m \le 10^5~.

Sample Input 1

4 4
1 2 1
2 3 2
3 1 1
1 4 100

Sample Output 1

3

Sample Input 2

3 2
1 2 1
1 3 19

Sample Output 2

0

Sample Input 3

3 4
1 2 1
2 1 2
1 2 3
1 3 100

Sample Output 3

5

Note