// Arup Guha
// 7/6/2025
// Solution to SI@UCF CP Camp Contest #1 Problem: Running Errands

import java.util.*;

public class errands {
	
	// Const for problem.
	final public static int ERRAND_COST = 5;

	public static int n;
	public static ArrayList<Integer>[] prereq;
	public static int[][] dist;
	
	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process cases.
		for (int loop=0; loop<nC; loop++) {
		
			n = stdin.nextInt();
			n++;
			int m = stdin.nextInt();
			
			// Originally all false.
			prereq = new ArrayList[n];
			for (int i=0; i<n; i++)
				prereq[i] = new ArrayList<Integer>();
			dist = new int[n][n];
			
			// Read distances.
			for (int i=0; i<n; i++)
				for (int j=0; j<n; j++)
					dist[i][j] = stdin.nextInt();
			
			// Get pre-requisites.
			for (int i=0; i<m; i++) {
				int x = stdin.nextInt();
				int y = stdin.nextInt();
				prereq[y].add(x);
			}
			
			// Set it up and run it!
			boolean[] used = new boolean[n];
			int[] perm = new int[n];
			used[0] = true;
			System.out.println(go(perm, used, 1));
		}
	}
	
	// Returns the best answer with the first k items fixed in perm.
	public static int go(int[] perm, boolean[] used, int k) {
	
		// We're done.
		if (k == n) return eval(perm);
		
		int res = 1000000000;
		
		// Try each possible item in slot k.
		for (int i=0; i<n; i++) {
		
			// Been here already.
			if (used[i]) continue;
			
			// Pre-reqs for i haven't been met.
			if (!met(used, i)) continue;
			
			// Place this item.
			used[i] = true;
			perm[k] = i;
			
			// Try this.
			int tmp = go(perm, used, k+1);
			
			// Update result if necessary.
			res = Math.min(res, tmp);
			
			// Undo so we can try something new.
			used[i] = false;
		}
		
		// Ta da!
		return res;
	}
	
	// Returns true iff all the pre-reqs for item are met. used stores which items
	// have been used (used[i] == true iff we've done these items.)
	public static boolean met(boolean[] used, int item) {
	
		// If any of these aren't used yet, then the prereq is NOT met.
		for (Integer x: prereq[item])
			if (!used[x])
				return false;
				
		// If we get here, the pre-req is met.
		return true;
	}
	
	// Returns the time for this permutation.
	public static int eval(int[] perm) {
		
		// Cost of errands is forced.
		int res = ERRAND_COST*(n-1);
		
		// Add up the travel costs.
		for (int i=0; i<n; i++)
			res += dist[perm[i]][perm[(i+1)%n]];
		return res;
	}
}