Đất nước Kc97ble có thành phố được nối bởi tuyến đường hai chiều, tuyến đường thứ nối liền hai thành phố và . Chính phủ đất nước Kc97ble mong muốn xây dựng thư viện tại một số thành phố trong đất nước, sao cho từ bất kì một thành phố nào cũng đều có thể đi đến một thành phố có thư viện.
Biết rằng chi phí xây dựng thư viện ở thành phố là . Hãy tính tổng chi phí xây dựng thư viện nhỏ nhất có thể.
Dữ liệu vào:
Dòng đầu tiên gồm hai số nguyên và - số thành phố và số tuyến đường;
Dòng thứ hai gồm số nguyên - với là chi phí xây dựng thư viện ở thành phố ;
dòng tiếp theo, dòng thứ gồm hai số nguyên và - mô tả tuyến đường thứ . Dữ liệu vào đảm bảo mỗi cặp thành phố được nối bởi nhiều nhất một tuyến đường.
Dữ liệu ra:
In ra tổng chi phí xây dựng thư viện nhỏ nhất có thể.
Ví dụ:
Dữ liệu vào:
5 4
6 4 2 3 3
1 2
2 4
4 1
3 5
Dữ liệu ra:
5
Giải thích
Ở ví dụ trên, ta có thể xây dựng thư viện ở thành phố và với tổng chi phí . Khi đó:
Từ thành phố có thể đi đến thành phố (thành phố có thư viện)
Từ thành phố có thể đi đến thành phố (thành phố có thư viện)
