#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define N 2005#define INF 0x3f3f3f3f#define LL __int64#define INF 0x3f3f3f3fint ma[N][N],d[N],vis[N],pre[N],dis[N][N],b[N];int judge(int x,int y,int v0){    int s1[2000],s2[2000],len1 = 0,len2 = 0,i,j;    s1[len1++] = y,s2[len2++] =y;    while(y!=v0) {s1[len1++] = pre[y];y = pre[y];}    s2[len2++] = x;    while(x!=v0) {s2[len2++] = pre[x];x = pre[x];}    for(i = len1-1,j = len2-1 ; i>=0&&j>=0 ; i--,j--)        if(s1[i]<s2[j]) return 0;        else if(s1[i]>s2[j]) return 1;        if(i<0&&j>=0) return 0;        else if(i>=0&&j<0) return 1;    return 1;}void dijkstral(int v0,int n){    int v,x,y,temp,i;    for(i = 1 ; i <= n ; i++)    {        d[i] = dis[v0][i];        if(d[i]!=INF) pre[i] = v0;        vis[i] = 0;    }    d[v0] = 0;    vis[v0] = 1;    for(i = 1 ; i <= n ; i++)    {        temp = INF;        for(y = 1 ; y <= n ;y++)            if(!vis[y]&&temp>d[y]) temp = d[x=y];        vis[x] = 1;        for(y = 1 ; y <= n ; y++)            if(!vis[y]&&d[x]+dis[x][y]<d[y])            {                 d[y] = d[x]+dis[x][y];                 pre[y] = x;            }            else if(!vis[y]&&d[x]+dis[x][y]==d[y])//判断字典序            {                if(judge(x,y,v0)) pre[y] = x;            }    }}int main(){    int n,m,i,j,k,s,t;    while(~scanf("%d",&n),n)    {        for(i = 1 ; i<= n ; i++)            for(j = 1 ; j<= n ; j++)            {                scanf("%d",&ma[i][j]);                if(ma[i][j] == -1) ma[i][j] = INF;            }            for(i = 1 ; i<= n ;i++) scanf("%d",&b[i]);            while(~scanf("%d %d",&s,&t))            {                if(s==-1&&t==-1) break;                for(i = 1 ; i<=n ; i++)                {                    for(j = 1 ; j <= n ;j++)                        if(j!=s&&j!=t) dis[i][j] = ma[i][j]+b[j];                    else dis[i][j] = ma[i][j];                }            dijkstral(s,n);            printf("From %d to %d :\n",s,t);            printf("Path: %d",s);            int sta[2000],i=0,p = t;            while(p!=s){                sta[i++] = p;                p = pre[p];            }            for(j = i -1; j>=0 ; j--)                printf("-->%d",sta[j]);            printf("\nTotal cost : %d\n\n",d[t]);            }    }    return 0;}