S国有n个城市，从a城到b城运货的花费有两部分组成：<o:p></o:p>
（1）a城到b城的运输费<o:p></o:p>
（2）途径城市的税收<o:p></o:p>
例如：a 运货到 b，走路线a —> i —> j —> b ,总花费为a 到 i ，i 到 j，j 到 b 的运输费、i，j 城市的税收之和。<o:p></o:p>
已知任意两个城市的运输费用，每个城市的税收，计算出，城市a到b的最小运输费。<o:p></o:p>
货物运输
Input
多组数据。
第一行输入整数n(n不大于200，城市从1开始编号)
接下来输入n行n列的矩阵M，Mij 表示 i 城市到 j 城市的运输费，-1表示这两个城市不能直接到达。
第n+2 行 输入n个整数，第i个整数代表第i个城市的税收。
第n+3 行 输入整数m，表示有m次询问（m不大于200）。
接下来m行，每行输入两个整数u， v。
第一行输入整数n(n不大于200，城市从1开始编号)
接下来输入n行n列的矩阵M，Mij 表示 i 城市到 j 城市的运输费，-1表示这两个城市不能直接到达。
第n+2 行 输入n个整数，第i个整数代表第i个城市的税收。
第n+3 行 输入整数m，表示有m次询问（m不大于200）。
接下来m行，每行输入两个整数u， v。
Output
对于每次询问
输出如下：
From u to v :
Path: u-->c1-->......-->ck-->v
Total cost :
............
From e to f :
Path: e-->e1-->..........-->ek-->f
Total cost : ......
Note: 如果有多种路径方案，输出字典序最小的，每次询问后加一个换行。a城市到a城市的运费不一定为0
输出如下：
From u to v :
Path: u-->c1-->......-->ck-->v
Total cost :
............
From e to f :
Path: e-->e1-->..........-->ek-->f
Total cost : ......
Note: 如果有多种路径方案，输出字典序最小的，每次询问后加一个换行。a城市到a城市的运费不一定为0
Sample Input
4
0 5 15 -1
5 0 5 8
15 10 2 5
-1 -1 8 0
5 3 7 1
3
1 3
2 4
3 1
Sample Output
</p>From 1 to 3 :
Path: 1-->2-->3
Total cost : 13
From 2 to 4 :
Path: 2-->4
Total cost : 8
From 3 to 1 :
Path: 3-->1
Total cost : 15