// Michael Galletti
// 3/12/2014
// Solution to FHSPS Problem: Twelve Years a Slave(twelve)

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

public class twelve_galletti {
	public static void main(String[] args) throws Exception{
		Scanner reader = new Scanner(new File("twelve.in"));
		
		//Read in number of city locations, create adjacency matrix
		int n = reader.nextInt();
		int[][] g = new int[n][n];
		
		//Read adjacency matrix from input
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				g[i][j] = reader.nextInt();
		
		//Run Floyd–Warshall algorithm to find all pairs shortest paths
		//g[i][j] will now contain the shortest path from node i to node j
		for(int k = 0; k < n; k++)
			for(int i = 0; i < n; i++)
				for(int j = 0; j < n; j++)
					if(g[i][j] > g[i][k] + g[k][j])
						g[i][j] = g[i][k] + g[k][j];
		
		//Process queries
		int paths = reader.nextInt();
		for(int p = 0; p < paths; p++){
			int s = reader.nextInt(); //Starting location
			int e = reader.nextInt(); //Ending location
			int t = reader.nextInt(); //Allotted time
			
			//For each odd-numbered location i (a cinema we could stop in), 
			//see if the shortest path from s to i plus the shortest path from i to t 
			//plus the running time of the film is within our time budget
			int cnt = 0;
			for(int i = 1; i < n; i += 2) //i starts at 1 and increments by 2 on each iteration
				if(g[s][i] + g[i][e] + 134 <= t)
					cnt++;
			
			//Output number of possible cinemas
			System.out.println(cnt);
		}
	}
}