// Adam Campbell
// 3/10/05
// Solution to COP 3530 Homework #3 Programming Problem

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

public class Railroad{

	private static int numCities;
	private static ArrayList cities;

	public static void main(String[] args) throws Exception{

		BufferedReader fileReader = new BufferedReader(new FileReader("railroad.in"));
		StringTokenizer tokenizer;
		int n; // num testcases
		int m; // num edges
		Edge[] edges; // list of edges from input
		Heap heap;
		DisjointSet disjointSet;
		int[][] adj; // adjacency, weight matrix
		String name1, name2; // name of the two cities from a line in the input
		int weight; // weight from the input
		int index1, index2; // the city names are mapped to numbers for easy implementation of DisjointSet
		String[] finalStrings; // the outputs
		Edge[] edgesInMST; // the edges in the final MST
		Edge topEdge; // the top edge from the Heap
		int numEdgesInMST; // number of edges currently in the MST
		int totalWeight; // total weight of the MST

		// read in the number of test cases
		n = Integer.parseInt(fileReader.readLine());
		
		// loop through all test cases
		while(n-- > 0){

			// read in the number of edges for this test case
			m = Integer.parseInt(fileReader.readLine());

			// initialize the edges and cities data structures
			edges = new Edge[m];
			cities = new ArrayList();
			
			// read in all of the edges
			for(int i = 0; i < m; i++){

				// read in the i^th edge
				tokenizer = new StringTokenizer(fileReader.readLine());

				name1 = tokenizer.nextToken();
				name2 = tokenizer.nextToken();
				weight = Integer.parseInt(tokenizer.nextToken());

				// obtain the city->index mapping
				index1 = getIndex(name1);
				index2 = getIndex(name2);

				// create the new edge
				edges[i] = new Edge(index1, index2, weight);

			}

			// the number of cities is equal to the size of the cities ArrayList
			numCities = cities.size();
			
			// make the heap
			heap = new Heap(m);
			for(int i = 0; i < m; i++){
				heap.add(edges[i]);
			}

			disjointSet = new DisjointSet(numCities);
			edgesInMST = new Edge[numCities - 1];
			numEdgesInMST = totalWeight = 0;

			// find the MST
			while(numEdgesInMST < numCities - 1){

				// get the smallest, unused edge from the Heap
				topEdge = (Edge)heap.removeTop();

				index1 = topEdge.index1;
				index2 = topEdge.index2;

				// if the two cities are in different sets, then connect them
				if(disjointSet.find(index1) != disjointSet.find(index2)){
					totalWeight += topEdge.weight;
					edgesInMST[numEdgesInMST++] = topEdge;
					disjointSet.union(index1, index2);
				}

			}

			finalStrings = new String[numCities - 1];

			// create the final list of edges that will be output
			for(int i = 0; i < finalStrings.length; i++){

				String city1 = (String)cities.get(edgesInMST[i].index1);
				String city2 = (String)cities.get(edgesInMST[i].index2);
				
				finalStrings[i] = (city1.compareTo(city2) < 0 ? city1 : city2) + " " + 
						  (city1.compareTo(city2) < 0 ? city2 : city1) + " " + 
						  edgesInMST[i].weight;

			}

			// sort the edges in the MSt
			Arrays.sort(finalStrings);

			System.out.println("The minimum cost of the railway system is " + totalWeight + ".");

			for(int i = 0; i < finalStrings.length; i++){
				System.out.println(finalStrings[i]);
			}

			System.out.println();
			
		}

	}

	// returns the index of this city
	// this is where we map a city name to a unique number
	private static int getIndex(String cityName){
	
		if(cities.contains(cityName)){
			return cities.indexOf(cityName);
		}else{
			cities.add(cityName);
			return cities.size()-1;
		}
		
	}
	
	// the Edge class implements Comparable so we can use the Heap class
	private static class Edge implements Comparable{

		public int index1, index2;
		public int weight;

		// simple edge constructor
		public Edge(int i1, int i2, int w){

			this.index1 = i1;
			this.index2 = i2;
			this.weight = w;

		}

		/* returns -1 if this < that
		 * returns 1 if this > that
		 * returns 0 otherwise
		 **/
		public int compareTo(Object obj){

			Edge that = (Edge)obj;

			if(this.weight < that.weight) return -1;
			if(this.weight > that.weight) return 1;

			return 0;

		}

	}

}