// Arup Guha
// 2/19/2016
// Solution to 2016 FHSPS Playoff Problem: Host City

import java.util.*;

public class city {

	// What we store for each city.
	private String cityName;
	private int hotelCost;
	private int numTeachers;

	public city(String name, int hotel, int teachers) {
		cityName = name;
		hotelCost = hotel;
		numTeachers = teachers;
	}

	public String toString() {
		return cityName;
	}

	public int getCost(city[] list, int[][] adj) {

		// Find which city is this city.
		int curCity = 0;
		for (int i=0; i<list.length; i++) {
			if (cityName.equals(list[i].cityName)) {
				curCity = i;
				break;
			}
		}

		// Add up travel costs.
		int cost = 0;
		for (int i=0; i<list.length; i++) {

			// No cost for all teachers in this city.
			if (i == curCity) continue;

			// This is the cost of the hotel for all teachers from city i.
			cost += hotelCost*list[i].numTeachers;

			// This is the cost of travel for all teachers from city i.
			cost += adj[i][curCity]*list[i].numTeachers;
		}

		// Our final answer.
		return cost;
	}

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process each case.
		for (int loop=0; loop<numCases; loop++) {

			// Read in info for each city.
			int n = stdin.nextInt();
			city[] list = new city[n];
			for (int i=0; i<n; i++) {
				String name = stdin.next();
				int hotel = stdin.nextInt();
				int teachers = stdin.nextInt();
				list[i] = new city(name, hotel, teachers);
			}

			// Read in the travel costs.
			int[][] adj = new int[n][n];
			for (int i=0; i<n; i++)
				for (int j=0; j<n; j++)
					adj[i][j] = stdin.nextInt();

			// Initially set first city as best.
			int best = 0, bestCost = list[0].getCost(list, adj);

			// Try the rest, update only if strictly better, of if equal but comes first alphabtically.
			for (int i=1; i<n; i++) {
				int curCost = list[i].getCost(list, adj);
				if (curCost < bestCost || (curCost == bestCost && list[i].toString().compareTo(list[best].toString()) < 0)) {
					best = i;
					bestCost = curCost;
				}
			}

			// Print out the result.
			System.out.println(list[best]);
		}
	}
}