Câu 4 (2,0 điểm). Chi phí vận chuyển tối thiểu 
Một doanh nghiệp vận chuyển luôn đảm bảo việc vận chuyển hàng hoá giữa n thành phố. Giữa hai thành phố có thể có hoặc không có tuyến đường vận chuyển trực tiếp. Doanh nghiệp phải lập kế hoạch thực hiện m vận đơn của khách hàng. Mỗi vận đơn là một yêu cầu vận chuyển một kiện hàng từ một thành phố nào đó đến một thành phố khác. Chi phí vận chuyển bao gồm hai phần:
1. Chí phí vận chuyển khi đi theo các tuyến đường giữa hai thành phố;
2. Chi phí cho việc phải đi qua mỗi thành phố trên tuyến đường vận chuyển, ngoại trừ thành phố xuất phát và thành phố kết thúc.
Yêu cầu: Tìm tuyến đường vận chuyển với chi phí nhỏ nhất cho mỗi vận đơn.
Dữ liệu vào: Cho trong tệp văn bản PHIVC.INP có cấu trúc như sau:
Dòng 1: Ghi hai số nguyên dương n, m trong đó n là số lượng thành phố, m là số lượng vận đơn. 
Dòng 2: Ghi n số nguyên dương b1, b2, ..., bn, trong đó bi là chi phí phải trả khi đi qua thành phố i.
Dòng thứ i trong n dòng tiếp theo: Mỗi dòng ghi n số nguyên ai1, ai2, ..., ain, trong đó aij là chi phí đi theo tuyến đường nối trực tiếp giữa thành phố i và thành phố j. Qui ước aij = -1 nếu không có tuyến đường trực tiếp nối thành phố i với thành phố j.
Dòng thứ k trong m dòng tiếp theo: Ghi hai số nguyên dương dk, ck là thành phố xuất phát và thành phố kết thúc trong vận đơn thứ k.
(2 < n ≤ 100; 1 ≤ m ≤ 100; 1 ≤ i, j ≤ n;  0 ≤ aij ≤ 2×107; 0 ≤ bi ≤ 2×107)
Dữ liệu ra: Ghi ra tệp văn bản PHIVC.OUT theo cấu trúc như sau:
Dữ liệu ghi gồm m dòng, dòng thứ k ghi chi phí vận chuyển theo tuyến đường tìm được ứng với vận đơn thứ k.
Ví dụ:
PHIVC.INP   
5 3
5     17   8    3    1
0     3   22   -1    4
3     0     5   -1   -1
22   5     0    9    20
-1   -1    9    0    4
4    -1    20   4    0
1   3
3   5
2   4
PHIVC.OUT
21
16
17

-------------hÕt-------------