523

#include <iostream>
#include <sstream>
#include <string>
#include <string.h>
#include <stdio.h>

#define INF 10000000

using namespace std;

int graph[105][105];
int tax[105];
int nxt[105][105];
int par[105];
int cnt;


int path(int i,int j)
{
	cout<<"Path: ";
	if(i==j)
	{
		cout<<i<<"-->"<<j<<"\n";
		return 0;
	}

	cout<<i<<"-->";
	while(i!=j)
	{
		i=nxt[i][j];
		if(i==j)
		cout<<i;
		else
		cout<<i<<"-->";
	}
	cout<<"\n";
	return 0;
}

int main()
{
	int t,n,src,dst;
	char ch;
	string s;
	stringstream ss;

	cin>>t;
	getchar();

	while(t--)
	{
		for(int i=0;i<105;i++)
		{
			for(int j=0;j<105;j++)
			nxt[i][j]=j;
		}
		getline(cin,s);
		if(s=="")
		{
			getline(cin,s);
		}
		ss.clear();
		ss<<s;
		cnt=0;
		while(ss>>n)
		{
			cnt+=1;
			if(n==-1)
				n=INF;
			graph[1][cnt]=n;

		}

		for(int i=2;i<=cnt;i++)
		{
			for(int j=1;j<=cnt;j++)
			{
				//cin>>n;
				scanf("%d%c",&n,&ch);
				if(n==-1)
				n=INF;
				graph[i][j]=n;
			}

		}
		for(int i=1;i<=cnt;i++)
		{
			//cin>>n;
			scanf("%d%c",&n,&ch);
			tax[i]=n;
		}

		for(int z=1;z<=cnt;z++)
		{
			for(int x=1;x<=cnt;x++)
			{
				for(int y=1;y<=cnt;y++)
				{
					if(graph[x][y]>(graph[x][z]+graph[z][y]+tax[z]))//+tax[z]
					{
						graph[x][y]=graph[x][z]+graph[z][y]+tax[z];//+tax[z];
						nxt[x][y]=nxt[x][z];
					}

				}
			}
		}
		while(1)
		{
			stringstream sss;
			getline(cin,s);
			if(s=="")
			break;
			sss<<s;
			for(int k=0;k<2;k++)
			{
				sss>>n;
				if(k)
				dst=n;
				else
				src=n;
			}

			cout<<"From "<<src<<" to "<<dst<<" :\n";
			path(src,dst);
			cout<<"Total cost : ";
			cout<<graph[src][dst]<<"\n";
			if(t)
			puts("");
		}

	}

	return 0;
}