Sau khi giải được bài toán Dãy con tăng trọng số, Steve nhận được phần thưởng là một chuyến du lịch tới một đất nước Alpha vô cùng xinh đẹp. Đất nước này gồm có thành phố và con đường hai chiều kết nối các thành phố với nhau. Điều kì lạ ở đất nước này là nếu Steve muốn đi qua một con đường nào đó, cậu phải đưa ra cho người quản lí con đường đó xem một số đồng xu với đủ mệnh giá khác nhau. Lưu ý rằng Steve chỉ cần cho họ xem những đồng xu đó thôi nên mỗi đồng xu có thể được sử dụng lại ở nhiều con đường khác nhau. Đương nhiên, trước đó cậu sẽ phải đổi tiền của mình lấy những đồng xu của đất nước này rồi, mệnh giá tiền xu ở đây cũng rất đặc biệt: có mệnh giá tiền xu trong đó luôn có . Steve muốn xuất phát tại một thành phố bất kì và đi thăm thú tất cả thành phố của đất nước Alpha nhưng cũng không muốn phải đổi quá nhiều tiền, nên cần tính toán tổng mệnh giá các đồng xu phải đổi nhỏ nhất để dù xuất phát ở thành phố nào cũng có thể đi thăm
tất cả thành phố.
Yêu cầu: Cho trước thông tin thành phố, con đường và mệnh giá các đồng xu cần có để đi qua từng con đường. Hãy giúp Steve xác định tổng mệnh giá các đồng xu phải đổi nhỏ nhất để Steve có thể đi thăm tất cả thành phố.
Dữ liệu:
Dòng đầu tiên gồm ba số nguyên dương ;
Dòng thứ hai gồm số nguyên là các mệnh giá của đồng xu;
Dòng thứ trong dòng tiếp theo: ba số nguyên dương đầu tiên với là số hiệu hai thành phố, là số lượng đồng xu mà Steve phải đưa cho người quản lí xem khi đi qua con đường nối giữa thành phố và , số tiếp theo là các số nguyên dương biểu diễn thứ tự của các đồng xu trong dãy đồng xu.
Kết quả:
Đưa ra một dòng ghi một số nguyên duy nhất là đáp án bài toán. Nếu không tồn tại cách đổi tiền thỏa mãn, in ra .
Ví dụ:
Dữ liệu:
3 3 4
1 2 5 10
1 2 2 1 2
1 3 1 3
2 3 1 4
Kết quả:
8
Giải thích:
Chọn các đồng xu thứ có tổng mệnh giá là , ta có thể thăm tất cả thành phố bằng cách đi qua các con đường nối thành phố và , và .
