Xây dựng đường đua
Thành phố ACM quyết định tổ chức một cuộc đua xe hậu Valentine. Thành phố gồm n nút giao thông và không có con đường nào nối 2 nút giao thông bất kỳ. Vì vậy ban tổ chức (BTC) muốn xây dựng các đường đua nối các nút giao thông lại với nhau tạo thành các vòng đua. Sau khi tham khảo giá cả từ công ty MCA, BTC đưa ra một danh sách gồm m con đường một chiều nối giữa 2 nút giao thông có thể xây dựng và giá của chúng. Vì muốn xây dựng thật nhiều vòng đua (như vậy sẽ có nhiều cuộc đua diễn ra song song), BTC muốn tất cả các nút giao thông đều được sử dụng trong cuộc đua và mỗi nút giao thông chỉ thuộc đúng một vòng đua (nghĩa là từ một nút giao thông chỉ có thể di chuyển tới các nút giao thông khác thuộc cùng một vòng đua). Chi phí xây dựng cuộc đua là tổng chi phí xây dựng các vòng đua, trong đó chi phí xây dựng một vòng đua là tổng chi phí xây dựng các đường đua thuộc vòng đua đó. Các NTUCoders hãy giúp BTC chọn các con đường cần xây dựng sao cho tổng chi phí là bé nhất nhé!
Chú ý: Các nút giao thông x1, x2, x3, ..., xk tạo thành một vòng đua nếu như ta có đường đi xi -> xi+1 -> xi+2 -> ... -> xi (1 <= i <= k).
Dữ liệu vào
Dòng thứ nhất chứa 2 số nguyên dương n và m
m dòng tiếp theo, dòng thứ i gồm 3 số u, v, w với ý nghĩa có thể xây dựng con đường nối từ u đến v với giá là w
Dữ liệu ra
In ra tổng chi phí bé nhất tìm được hoặc in ra -1 nếu không có cách xây dựng thỏa mãn yêu cầu bài toán
Giới hạn
1 <= n <= 500, 1 <= m <= n*(n-1)
1 <= w <= 109
Dữ liệu đảm bảo không có đường đua nào nối một nút giao thông với chính nó
Ví dụInput
| 6 8 |
| 1 2 3 |
| 2 3 2 |
| 3 1 6 |
| 2 4 3 |
| 4 6 1 |
| 6 5 2 |
| 5 4 3 |
| 5 3 4 |
Output
| 17 |
Giải thích: xây dựng các đường đua tạo thành 2 vòng đua: 1 -> 2 -> 3 và 4 -> 6 -> 5 với chi phí là 17
