Problem
Có N thành phố trong cả nước, một số thành phố được nối với nhau bằng đường bộ. Phải mất một thùng xăng để lái xe trên một con đường. Ở mỗi thành phố, một thùng xăng có giá khác nhau. Bạn cần đi từ thành phố đầu tiên đến thành phố thứ N, tiêu càng ít tiền càng tốt. Bạn không thể mua xăng để sử dụng trong tương lai.
Đầu vào
Dòng đầu tiên chứa số N (1≤N≤100), dòng tiếp theo chứa N số, số thứ i cho biết giá xăng của thành phố thứ i (đây là các số nguyên từ 0 đến 100 ). Sau đó là số M – số lượng đường trong nước, tiếp theo là mô tả về chính những con đường đó. Mỗi đường được cho bởi hai số – số lượng các thành phố mà nó kết nối. Tất cả các con đường đều là hai chiều (nghĩa là chúng có thể được lái theo cả hướng này và hướng khác), luôn không có nhiều hơn một con đường giữa hai thành phố, không có con đường nào dẫn từ thành phố đến chính nó.
Đầu ra
Bắt buộc phải xuất một số duy nhất – tổng chi phí của tuyến đường hoặc -1 nếu không thể đến đó.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
5
3 6 1 7 6
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
|
3 |