Hệ thống giao thông CSUH bao gồm tổng cộng ~N~ nút, các nút được đánh số từ ~1~ đến ~N~, giữa hai nút bất kỳ đều có chính xác một tuyến đường hai chiều nối giữa chúng. Vì vậy, hệ thống giao thông CSUH có tổng cộng ~\frac{N(N-1)}{2}~ tuyến đường.

Trong thời gian tới, lãnh đạo thành phố muốn chọn một số tuyến đường để tiến hành nâng cấp. Để tránh tình trạng "công trình nối dài", trong số các tuyến đường được chọn, không được tồn tại bất kỳ hai tuyến đường nào có chung nút. Ngoài ra, mỗi tuyến đường đều có một chi phí sửa chữa riêng, ban lãnh đạo thành phố muốn dự trù kế hoạch bằng cách tính toán chi phí cao nhất có thể để tiến hành nâng cấp tuyến đường.

Yêu cầu: Cho biết hệ thống giao thông CSUH, hãy xác định chi phí cao nhất có thể để nâng cấp tuyến đường.

Input

• Dòng đầu tiên gồm số nguyên ~N~ ~(2 \le N \le 16)~ ~-~ số nút của hệ thống giao thông.
• ~\frac{N(N-1)}{2}~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i~, ~v_i~ và ~w_i~ ~(~~1 \le u_i,v_i<N~, ~1 \le w_i \le 10^9~~)~ ~-~ tuyến đường thứ ~i~ nối hai nút ~u_i~ và ~v_i~ với chi phí sửa chữa ~w_i~.
• Dữ liệu đảm bảo giữa hai nút bất kỳ đều có chính xác một tuyến đường nối giữa chúng.

Output

• In ra chi phí cao nhất có thể để nâng cấp tuyến đường.

Examples

Sample Input

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

Sample Output

9

Scoring

• Subtask ~1~ với ~50\%~ số điểm: ~N \le 7~
• Subtask ~2~ với ~50\%~ số điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, có thể chọn tuyến đường thứ nhất (nối hai nút ~1~ và ~4~) với chi phí bằng ~5~ và tuyến đường thứ hai (nối hai nút ~2~ và ~3~) với chi phí bằng ~4~. Chi phí để nâng cấp tuyến đường là ~5+4=9~. Dễ dàng nhận thấy rằng không còn cách chọn các tuyến đường nào có tổng chi phí cao hơn.