#2024. GATHER

Cánh đồng của nông dân John là một địa điểm có đồng cỏ, được nối với nhau bằng con đường. Các con đường đảm bảo từ đồng cỏ luôn có cách di chuyển tới các đồng cỏ còn lại. Mỗi con đường có một độ dài nhất định.

Lễ hội sắp đến và đàn bò của nông dân John chuẩn bị gặp nhau! Tại đồng cỏ thứ hiện có con bò. Chúng sẽ gặp nhau tại một đồng cỏ duy nhất đang được lựa chọn. Hãy chọn phương án sao cho tổng khoảng cách di chuyển của các con bò là nhỏ nhất.

Dữ liệu vào:

• Dòng đầu chứa một số nguyên dương ;
• dòng sau, mỗi dòng chứa một số nguyên là số con bò đang có trên đồng cỏ tương ứng
• dòng tiếp theo, mỗi dòng chứa ba số nguyên mô tả một con đường nối hai đồng cỏ với , có độ dài .

Dữ liệu ra:

-Một số nguyên duy nhất là tổng khoảng cách di chuyển nhỏ nhất trong tình huống tối ưu.

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

15

Giải thích:

Địa điểm tối ưu là đồng cỏ số . Khi đó

• Con bò ở đồng cỏ di chuyển quãng đường
• Con bò ở đồng cỏ di chuyển quãng đường
• Con bò ở đồng cỏ di chuyển quãng đường
• Tổng khoảng cách:

(Đồng cỏ và cũng cho kết quả tối ưu tương tự)