/*
floyd记录最短字典序最小的路径
*/
#include<stdio.h>
#include<string.h>
#define N 550
#define inf 0x3fffffff
int dis[N][N],path[N][N];
int b[N];
int n;
void floyd()
{
    int i,j,k;
    for(k=1; k<=n; k++)
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            {
                if(dis[i][k]==inf||dis[k][j]==inf)continue;
                int tmp=dis[i][k]+dis[k][j]+b[k];
                if(dis[i][j]>tmp)
                {
                    dis[i][j]=tmp;
                    path[i][j]=path[i][k];
                }
                else if(dis[i][j]==tmp&&path[i][j]>path[i][k]) //同时判断字典序是否最小
                    path[i][j]=path[i][k];
            }
    return ;
}
int main()
{
    int i,j,k;
    while(scanf("%d",&n),n)
    {
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            {
                scanf("%d",&dis[i][j]);
                if(dis[i][j]==-1)dis[i][j]=inf;

                path[i][j]=j;
            }
        for(i=1; i<=n; i++)
            scanf("%d",&b[i]);
        floyd();
        int s,t;
        while(scanf("%d%d",&s,&t),s!=-1&&t!=-1)
        {
            printf("From %d to %d :\n",s,t);
            printf("Path: ");
            printf("%d",s);
            k=s;
            while(k!=t)
            {
                k=path[k][t];
                printf("-->%d",k);
            }
            printf("\n");
            printf("Total cost : %d\n\n",dis[s][t]);
        }
    }
    return 0;
}