题目描述

这是春国的N个城市。每对城市之间可能有一条运输轨道，也可能没有。现在有一些货物需要从一个城市运送到另一个城市。运输费由两部分组成：在这些城市之间的路径上的运输费用，以及货物经过一个城市时征收的一定税费，除了始发地和目的地城市外。
您必须编写一个程序来找到成本最小的路线。

输入格式

题目包含多组数据。
第一个是N，城市数量。N = 0 表示输入结束。
输入中给出了运输费用、城市税、来源城市和目的地城市的数据，其形式为：
a11 a12 ... a1N
a21 a22 ... a2N
........................ ..
aN1 aN2 ... aNN
b1 b2 ... bN

c d
e f
...
g h

其中 aij 是从城市 i 到城市 j 的运输成本，aij = -1 表示城市 i 和城市 j 之间没有直接路径。
bi代表经过i城市的税费。
货物要从c城市发往d城市，e城市发往f城市，……，g=h=-1。

输出格式

您必须输出每组经过的城市顺序和总成本，其形式为：
From c to d :
Path: c-->c1-->......-->ck-->d
Total cost : ......
......

From e to f :
Path: e-->e1-->..........-->ek-->f
Total cost : ......

注意：如果有多个最小路径，则输出字典序最小的一个。每个测试用例后打印一个空行。

样例数据

input

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

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

数据范围

2<=N<=300