#1413. ROADADS - Quảng cáo ven đường

Một cuộc thi lập trình Olympic Tin học Quốc gia được tổ chức với nhà tài trợ khác nhau. Vì vậy, Ban tổ chức (BTC), muốn đặt các quảng cáo trên các con đường nối nhà tài trợ này. Ông ấy muốn đảm bảo rằng bất kỳ ai cũng sẽ nhìn thấy các quảng cáo trên mọi con đường họ đi qua giữa các cặp địa điểm đặt văn phòng của các nhà tài trợ. Vì vậy, bất kỳ con đường nào trên con đường ngắn nhất nối bất kỳ cặp địa điểm trong số nhà tài trợ đều phải được lắp đặt quảng cáo ven đường.

Chi phí để đặt một quảng cáo trên con đường đó đã được biết trước. Tổng chi phí của chiến dịch quảng cáo này là tổng của các chi phí đặt biển quảng cáo trên các con đường. BTC muốn tìm chi phí tối thiểu cần thiết để đạt được mục tiêu của mình.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương – số lượng các địa điểm thuộc thành phố tổ chức cuộc thi.
• dòng tiếp theo, mỗi dòng chứa ba số nguyên thể hiện nếu đặt biển quảng cáo trực tiếp giữa hai địa điểm và thì mất chi phí là ;
• Dòng tiếp theo là – số lượng truy vấn;
• dòng tiếp theo, mỗi dòng chứa số nguyên là địa điểm của nhà tài trợ cuộc thi, trong đó đôi một khác nhau.

Dữ liệu ra:

• Gồm dòng, mỗi dòng là tổng chi phí đặt biển quảng nhỏ nhất tương ứng với nhà tài trợ được cho trong dữ liệu vào.

Ví dụ:

Dữ liệu vào:

6
4 0 4
0 1 2
1 3 9
3 5 1
3 2 5
2
4 0 3 5 2
0 4 1 3 5

Dữ liệu ra:

21
16

Giới hạn:

• Subtask số điểm có ;
• Subtask số điểm khác có , mỗi địa điểm nối tối đa tới hai đỉnh khác;
• Subtask số điểm khác có ;
• Subtask số điểm còn lại có .