// Arup Guha
// 4/22/2017
// Solution for 2017 Round 1B Code Jam Problem C (large)
// Should have figured it out when I did the small...

import java.util.*;

public class c {
	
	public static void main(String[] args) {
		
		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process all of the cases.		
		for (int loop=1; loop<=numCases; loop++) {
			
			// Read in the input.
			int n = stdin.nextInt();
			int q = stdin.nextInt();
			
			int[] maxHorse = new int[n];
			int[] horseSpeed = new int[n];
			for (int i=0; i<n; i++) {
				maxHorse[i] = stdin.nextInt();
				horseSpeed[i] = stdin.nextInt();
			}
			
			long[][] adj = new long[n][n];
			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					adj[i][j] = stdin.nextInt();
				}
			}
			
			// Run Floyd's on it to get shortest distances to each place.
			for (int k=0; k<n; k++) {
				for (int i=0; i<n; i++) {
					for (int j=0; j<n; j++) {
						if (adj[i][k] < 0 || adj[k][j] < 0) continue;
						
						if (adj[i][j] < 0 || adj[i][k]+adj[k][j] < adj[i][j])
							adj[i][j] = adj[i][k]+adj[k][j];
						
					}
				}
			}
			
			// Now, fill in the time for horse i to travel to point j in this graph.
			// I just put a bit number if it's too far.
			double[][] times = new double[n][n];
			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					if (i==j) times[i][i] = 0;
					else if (adj[i][j] != -1 && adj[i][j] <= maxHorse[i])
						times[i][j] = 1.0*adj[i][j]/horseSpeed[i];
					else
						times[i][j] = 1e15;
				}
			}
			
			// Then, run Floyd's again =)
			for (int k=0; k<n; k++)
				for (int i=0; i<n; i++)
					for (int j=0; j<n; j++)
						times[i][j] = Math.min(times[i][j], times[i][k]+times[k][j]);
			
			// Case header.
			System.out.print("Case #"+loop+":");
			
			// Do queries
			for (int i=0; i<q; i++) {
				int s = stdin.nextInt()-1;
				int e = stdin.nextInt()-1;
				System.out.printf(" %.9f", times[s][e]);
			}
			
			System.out.println();
		}
	}
}