Mô tả bài toán: Có $N$ thành phố, được đánh số từ $1$ đến $N$. Cho ma trận kề giữa các thành phố này, trong ma trận, giá trị $-1$ biểu thị hai thành phố không có đường nối trực tiếp, các giá trị khác biểu thị độ dài của đường đi. Nếu một chiếc xe ô tô đi qua một thành phố, thì cần trả một khoản phí đường bộ nhất định. Khi đi từ thành phố $a$ tới thành phố $b$, tổng chi phí bằng tổng độ dài của các đường đi cộng với tổng phí đường bộ của tất cả các thành phố đi qua, ngoại trừ thành phố đầu và cuối. Yêu cầu tìm chi phí nhỏ nhất. Nếu tồn tại nhiều đường đi thỏa mãn, thì in ra đường đi có thứ tự từ điển nhỏ nhất.

Input: Dòng đầu tiên là một số $N$, biểu thị số lượng thành phố, nếu $N = 0$ biểu thị kết thúc. Tiếp theo là $N$ dòng, dòng thứ $i$ gồm $N$ số $a_{i,1} \sim a_{i,n}$, trong đó $a_{i,j}$ biểu thị phí đường bộ trực tiếp giữa thành phố thứ $i$ và thành phố thứ $j$, nếu $a_{i,j} = -1$ nghĩa là không có đường nối trực tiếp. Dòng tiếp theo chứa $N$ số, số thứ $i$ biểu thị phí đường bộ của thành phố thứ $i$. Tiếp sau đó là rất nhiều dòng, mỗi dòng chứa hai số, biểu thị thành phố xuất phát và thành phố đích, nếu hai số là $-1$ thì kết thúc.

Output: Với mỗi cặp thành phố được cho, in ra các thành phố đi qua trên đường đi có chi phí nhỏ nhất và tổng chi phí nhỏ nhất. Định dạng output như sau:

From a to b:
Path: a-->a1-->...-->ak-->b
Total cost: ...

Input mẫu:

5
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
5 17 8 3 1
1 3
3 5
2 4
-1 -1
0

Output mẫu:

From 1 to 3:
Path: 1-->5-->4-->3
Total cost: 21
From 3 to 5:
Path: 3-->4-->5
Total cost: 16
From 2 to 4:
Path: 2-->1-->5-->4
Total cost: 17