Mirko và Slavko đang tích cực tập luyện cho cuộc đua marathon xe đạp đôi hằng năm tại Croatia. Họ cần chọn một lộ trình để tập luyện.

Đất nước của họ có \(N\) thành phố và \(M\) con đường. Mỗi con đường nối hai thành phố và có thể đi theo cả hai chiều. Đúng \(N-1\) con đường được trải nhựa; các con đường còn lại là đường mòn chưa trải nhựa. Mạng lưới đường được thiết kế sao cho giữa hai thành phố bất kỳ luôn có một đường đi chỉ gồm các đường đã trải nhựa. Nói cách khác, \(N\) thành phố cùng \(N-1\) đường trải nhựa tạo thành một cây.

Ngoài ra, mỗi thành phố là đầu mút của không quá \(10\) con đường, tính cả đường trải nhựa lẫn đường chưa trải nhựa.

Một lộ trình tập luyện bắt đầu tại một thành phố, đi qua một số con đường rồi quay về thành phố xuất phát. Mirko và Slavko thích đến những nơi mới, nên ngoài việc quay lại thành phố xuất phát để kết thúc lộ trình, họ không được đi qua một thành phố hai lần hoặc đi trên cùng một con đường hai lần. Có thể xuất phát ở bất kỳ thành phố nào và không bắt buộc phải đi qua tất cả các thành phố.

Người ngồi phía sau đạp nhẹ hơn vì được người phía trước che gió. Vì vậy, Mirko và Slavko đổi chỗ cho nhau tại mỗi thành phố. Để cả hai được tập luyện như nhau, họ phải chọn một lộ trình có số con đường là số chẵn.

Các đối thủ của họ quyết định chặn một số đường chưa trải nhựa để Mirko và Slavko không thể tìm được lộ trình tập luyện thỏa mãn các yêu cầu trên. Mỗi đường chưa trải nhựa có một chi phí chặn là số nguyên dương. Không thể chặn đường đã trải nhựa.

Cho mô tả mạng lưới thành phố và đường, hãy tìm tổng chi phí nhỏ nhất để chặn các đường sao cho không còn lộ trình tập luyện nào thỏa mãn các yêu cầu.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên \(N\) và \(M\), lần lượt là số thành phố và tổng số con đường.
• Mỗi dòng trong \(M\) dòng tiếp theo chứa ba số nguyên \(A\), \(B\), \(C\), mô tả một con đường nối trực tiếp hai thành phố khác nhau \(A\) và \(B\). Nếu \(C=0\), đây là đường trải nhựa. Nếu \(C>0\), đây là đường chưa trải nhựa và \(C\) là chi phí chặn đường đó.

Mỗi thành phố là đầu mút của không quá \(10\) con đường. Giữa một cặp thành phố không bao giờ có nhiều hơn một con đường nối trực tiếp.

Dữ liệu ra

Ghi một số nguyên duy nhất: tổng chi phí chặn đường nhỏ nhất để không còn lộ trình tập luyện hợp lệ.

Ràng buộc

• \(2 \le N \le 1\,000\).
• \(N-1 \le M \le 5\,000\).
• \(1 \le A,B \le N\) và \(A \ne B\).
• \(0 \le C \le 10\,000\).
• Đúng \(N-1\) đường có \(C=0\), và những đường này nối tất cả các thành phố thành một cây.

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Mỗi nhóm có trọng số 1. Có 11 nhóm tính điểm; điểm cuối cùng bằng \(100 \times W / 11\), với \(W\) là tổng trọng số các nhóm đạt. Mỗi nhóm đạt đóng góp chính xác \(100/11\) điểm; không làm tròn riêng từng nhóm.

Các ví dụ trong đề không tính điểm.

Ví dụ

5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1

5

9 14
1 2 0
1 3 0
2 3 14
2 6 15
3 4 0
3 5 0
3 6 12
3 7 13
4 6 10
5 6 0
5 7 0
5 8 0
6 9 11
8 9 0

48

Nguồn

IOI 2007, ngày thi thứ hai: Training.