/* Sample solution for CPSC 441 Assignment    */
/* Code source credit: thecrazyprogrammer.com */

#include<stdio.h>

#define MAX 24
#define INFINITY 9999
#define NAME_LENGTH 3
/* #define HOPS_ONLY 1 */
/* #define DEBUG 1 */
 
void dijkstra(int G[MAX][MAX],int n,int startnode);
 
/* Global variable */
char nodelist[MAX][NAME_LENGTH+1];

int main()
  {
    int G[MAX][MAX],i,j,n,u;
    
    /* Number of vertices */
    scanf("%d",&n);
    if( n > MAX )
      printf("Too many nodes!!!\n");

    /* Scan in the city names for each vertex */
    for(i=0;i<n;i++)
	scanf("%s\n", &nodelist[i]);

    /* Adjacency matrix with link costs */
    for(i=0;i<n;i++)
      {
	for(j=0;j<n;j++)
	  {
	    scanf("%d",&G[i][j]);
#ifdef DEBUG
	    if( G[i][j] > 0 )
	      printf("Distance from %s to %s is %d\n",
		     nodelist[i], nodelist[j], G[i][j]);
#endif
#ifdef HOPS_ONLY
	    if( G[i][j] > 0 )
	      G[i][j] = 1;
#endif
	    if( (i > j) && (G[i][j] != G[j][i]) )
	      printf("Sanity check: G[%d][%d] = %d != G[%d][%d] = %d\n",
		     i, j, G[i][j], j, i, G[j][i]);
	  }
      }
    printf("Adjacency matrix sanity check complete...\n");

    /* Specify start node */
    scanf("%d",&u);

    /* Determine the route */
    dijkstra(G,n,u);

    return 0;
  }
 
void dijkstra(int G[MAX][MAX],int n,int startnode)
  {
 
    int cost[MAX][MAX],distance[MAX],pred[MAX];
    int visited[MAX],count,mindistance,nextnode,i,j;

    //pred[] stores the predecessor of each node
    //count gives the number of nodes seen so far
    //create the cost matrix
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
	if(G[i][j]==0)
	  cost[i][j]=INFINITY;
	else
	  cost[i][j]=G[i][j];

    //initialize pred[],distance[] and visited[]
    for(i=0;i<n;i++)
      {
	distance[i]=cost[startnode][i];
	pred[i]=startnode;
	visited[i]=0;
      }
    distance[startnode] = 0;
    visited[startnode] = 1;
    count = 1;
    while(count < n-1)
      {
	mindistance=INFINITY;

	//nextnode gives the node at minimum distance
	for(i=0;i<n;i++)
	  if(distance[i]<mindistance&&!visited[i])
	    {
	      mindistance=distance[i];
	      nextnode=i;
	    }

	//check if a better path exists through nextnode
	visited[nextnode]=1;
	for(i=0;i<n;i++)
	  if(!visited[i])
	    if(mindistance+cost[nextnode][i]<distance[i])
	      {
		distance[i]=mindistance+cost[nextnode][i];
		pred[i]=nextnode;
	      }
	count++;
      }
 
    //print the path and distance of each node
    for(i=0;i<n;i++)
      if(i!=startnode)
	{
	  printf("\nDistance of node %d (%s)=%d",
		 i,nodelist[i],distance[i]);
	  printf("\nPath=%d (%s)",i, nodelist[i]);
	  j=i;
	  do
	    {
	      j=pred[j];
	      printf("<-%d (%s)",j, nodelist[j]);
	    }
	  while(j!=startnode);
	}
    printf("\n");
  }