// Arup Guha
// Written on 10/6/07 - edited version of an exam question solution from Fall 06.

import java.io.*;
import java.util.*;

// Stores information necessary to run Dijkstra's for each vertex in the graph.
class point {
	
	public Double distance;
	public boolean chosen;
	public int last;
	
	public point(double d, int source) {
		distance = new Double(d);
		last = source;
		chosen = false;
	}
}

public class home {
	
	// No path will be longer than this.
	final static int  MAXINT = 1000000000;
	final static double EPSILON = 10e-9;
	
	public static void main(String[] args) throws Exception {
		
		Scanner fin = new Scanner (new File("home.in"));
		double[][] adj;

		int numsets = fin.nextInt();

		for (int set=1; set<=numsets; set++) {
		
			// Read in this adjacency matrix.
			int n = fin.nextInt();
			adj = new double[n][n];
			for (int i = 0; i<n*n; i++)
				adj[i/n][i%n] = fin.nextDouble();
				
			// Get source and destination
			int source = fin.nextInt();
			int end = fin.nextInt();
			int saveend = end;
			
			// Run Dijkstra's and store the return array of shortest distances.
			point[] answers = dijkstra(adj, source);

			System.out.println("Map #"+set);

			// First part of the info we want.
			System.out.printf("The shortest distance between %d and %d is %.2f.\n", source, end, round(answers[end].distance));
		
			// Set up variables to reconstruct the desired path.
			String path = "";

			boolean firstTime = true;
				
			// We build the path up from the end, so when the end is the
			// source, we can stop.
			while (end != source) {
		
				// here we prepend the proper vertex to our path, working
				// backwards. The first time through, we don't add a -.
				if (firstTime) 
					path = end + path;
				else
					path = (end + "->") + path;
						
				// Now that we've added end to our path, our new end is the
				// vertex that we would go to BEFORE our old end.
				end = answers[end].last;
				
				// If we get here, we're done with our first iteration.
				firstTime = false;	
				
			} // end while for building path.

			// Now just add an edge from the source to what's already been
			// built.
			path = source + "->" + path;
		
			// Now we can print out the path.
			System.out.println("The shortest path from "+source+" to "+saveend+" is "+path+".");
			System.out.println();
		} // for set

		fin.close();

	} // end-main
	
	public static point[] dijkstra(double[][] adj, int source) {
		
		point[] estimates = new point[adj.length];
		
		// Set up our initial estimates.
		for (int i=0; i<estimates.length; i++)
			estimates[i] = new point(MAXINT, source);
			
		// This estimate is 0, now.
		estimates[source].distance = 0.0;
		
		// Really, we can run this n-1 times, where n is the number of
		// vertices. The last iteration does NOT produce any different paths.
		for (int i=0; i<estimates.length-1; i++) {
			
			// Pick the minimal vertex to add into, S, our set of vertices
			// for which we have shortest distances.
			int vertex = 0;
			double bestseen = MAXINT;
			
			// In order to be chosen here, you can not have been previously
			// chosen. Also, you have to be smaller than all other candidates.
			for (int j=0; j<estimates.length; j++) {
				if (estimates[j].chosen == false && 
				    estimates[j].distance < bestseen) {
				
					bestseen = estimates[j].distance;
					vertex = j;
				}
			}
			
			// Choose this vertex!
			estimates[vertex].chosen = true;
			
			// Update our estimates based on edges that leave from this vertex.
			for (int j = 0; j<estimates.length; j++) {
				
				// Do we get a shorter distance by traveling to vertex, and then
				// taking the edge from vertex to j? If so, make the update here.
				if (estimates[vertex].distance+adj[vertex][j] < 
				    estimates[j].distance) {
				    
				    // Our new estimate to get to j, going through vertex.
				    estimates[j].distance = estimates[vertex].distance + adj[vertex][j];	
				    
				    // This also means that vertex is the last vertex on the new
				    // shortest path to j, so we need to store this also.
				    estimates[j].last = vertex;
				}
			}
			
		}
		
		// We return these whole estimates array.
		return estimates;
	}
	
	// Return x rounded to two decimal spots.
	public static double round(double x) {
		
		// Get rid of everything past the second decimal.
		double intpart = (long)(x*100)/100.0;
		
		// Get the third digit after the decimal, EPSILON is for the round off errors...
		long lastdigit = (long)(x*1000+EPSILON)%10;
		
		// Need to round up.
		if (lastdigit >= 5)
			return intpart+.01;
		
		// We are fine.
		else
			return intpart;
	}
}