// Author: Marko Berezovsky

/*
  A particular *type* in this solution is a particular pokemon
  (the word pokemon is too long.)
	Start site which coords are (0, 0) is treated as a regular site with no types in it.
*/

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

public class Pokemon {

static int Nsites, Ntypes;
static int [] x, y;
static int [][] typesHere; // 0/1, sites * types
                           // each site has a characteristic 0/1 vector of
													 // types available in the site

static int [][] distVal, distWho; // distances to other sites, sorted
                                  // in ascending order on each row (= site)
	                                // Val store distances, Who stores ID's of the sites

static int bestDist;

static int noUnUsedTypes;
static int [] usedTypes;
static boolean [] usedSites;

static int [] path;  // debug arr
static int calls = 0;


// --------------------------------------------------------------------------

static void search( int site, int distSoFar, int depth ){
	//for( int j = 0; j < depth; j++ ) System.out.printf( "  ");
	//System.out.printf( "in site %d    noUnused %d\n", site, noUnUsedTypes  );
	path[depth] = site;
	calls++;

// all types collected?
	if( noUnUsedTypes == 0 ){
		//System.out.printf( "path: " );
		//for( int i = 0; i <= depth; i++ )
		//	System.out.printf( " %d ", path[i] );
		//System.out.printf( "   len  %d   best %d\n", distSoFar + distVal[site][0], bestDist );

		distSoFar += distVal[site][0];
		if( distSoFar < bestDist ) bestDist = distSoFar;
		distSoFar -= distVal[site][0];
		return;
	}

	// otherwise try to move to some another suitable site

	int neigh, newDist,  NNewTypes;
	for( int i_neigh = 1; i_neigh < Nsites; i_neigh++ ){
		neigh = distWho[site][i_neigh];
		if( usedSites[neigh] ) continue;

		// distance pruning
		newDist = distSoFar + distVal[site][i_neigh];
		if( newDist >= bestDist ) continue; // more involved?

		// brings new types?
		NNewTypes = 0;
		for( int j = 0; j < Ntypes; j++ )
			if( typesHere[neigh][j] > 0 && usedTypes[j] == 0 )
				NNewTypes++;
		if( NNewTypes == 0 ) continue;

		// recurse
		noUnUsedTypes -= NNewTypes;
		for( int j = 0; j < Ntypes; j++ ) usedTypes[j] += typesHere[neigh][j];
		usedSites[neigh] = true;

		search( neigh, newDist, depth+1 );

		usedSites[neigh] = false;
		for( int j = 0; j < Ntypes; j++ ) usedTypes[j] -= typesHere[neigh][j];
		noUnUsedTypes += NNewTypes;
	}
}

// ----------------------------------------------------------------------------
//                      M A I N
// ----------------------------------------------------------------------------


public static void main(String[] args) {
  loadAndInit();
	search(0, 0, 0);

	System.out.printf( "%d\n", bestDist );
	//System.out.printf( "calls %d\n", calls );
}



static void loadAndInit(){ try {
	BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
	StringTokenizer st = new StringTokenizer( br.readLine() );

	int N = 1+Integer.valueOf( st.nextToken() );
	x = new int [N];
	y = new int [N];

	String name = "";
	int xx, yy, pred;
	Ntypes = 0; Nsites = 0;
	ArrayList<String> names = new ArrayList();
	ArrayList<String> [] typHere = new ArrayList[N];
	for( int i = 0; i < N; i++ )
		typHere[i] = new ArrayList();

	x[0] = y[0] = 0; // start;
	Nsites = 1;

	for( int i = 1; i < N; i++ ){
		st = new StringTokenizer( br.readLine() );
		xx = Integer.valueOf( st.nextToken() );
		yy = Integer.valueOf( st.nextToken() );
		name =  st.nextToken();
		names.add( name );

		for( pred = 1; pred < i; pred++ )
			if( x[pred] == xx && y[pred] == yy ){ // find old site if it eex
				typHere[pred].add(name);
				break;
		}

		if( pred == i )
		  { x[Nsites] = xx; y[Nsites] = yy; typHere[Nsites++].add(name); }
	}

	/*
	System.out.printf( "N sites %d\n", Nsites );
	for( int i = 0; i < Nsites; i++ ){
		System.out.printf( "%3d %3d ",  x[i], y[i] );
		for( String s : typHere[i] )
			System.out.printf( "  %s ", s );
		System.out.printf( "\n" );
	}
		*/

	Collections.sort(names);

	/*
	   for( int j = 0; j < names.size(); j++ )
		   System.out.printf( " .%s.  ",  names.get(j));
	   System.out.printf( "\n" );
	*/

	Ntypes = 1;
	int w = 1;
	while( w < names.size() )
		if( names.get(w).equals(names.get(w-1)) )
			names.remove(w);
		else w++;

	Ntypes = names.size();

	/*
	for( int j = 0; j < names.size(); j++ )
		System.out.printf( " .%s.  ",  names.get(j));
	System.out.printf( "\n" );
	System.out.printf( "N types %d\n", Ntypes );
	*/

	typesHere = new int [Nsites][Ntypes];
	for( int i = 0; i < Nsites; i++ )
		for( String typename : typHere[i] )
			typesHere[i][names.indexOf(typename)] = 1;

	/*
	for( int i = 0; i < Nsites; i++ ) {
		for( int j = 0; j < Ntypes; j++ )
			System.out.printf( "%d  ", typesHere[i][j] );
		System.out.printf( "\n" );
	}
	*/

	path = new int [Nsites];

	usedTypes = new int[Ntypes];
	usedSites = new boolean[Nsites];
	noUnUsedTypes = Ntypes;
	bestDist = Integer.MAX_VALUE;


	distVal = new int[Nsites][Nsites];
	distWho = new int[Nsites][Nsites];


	for( int i = 0; i < Nsites; i++ )
		for( int j = 0; j < Nsites; j++ ) {
			distVal[i][j] = distVal[j][i] = Math.abs(x[i]-x[j]) + Math.abs(y[i]-y[j]);
			distWho[i][j] = j;
			distWho[j][i] = i;
		}

	/*
	System.out.printf( "\n" );
	for( int i = 0; i < Nsites ; i++ ){
		for( int j = 0; j < Nsites ; j++ )
			System.out.printf( " %2d[%2d] ", distWho[i][j], distVal[i][j] );
		System.out.printf( "\n" );
	}
	*/

	sortDists();

	/*
	System.out.printf( "\n" );
	for( int i = 0; i < Nsites ; i++ ){
		for( int j = 0; j < Nsites ; j++ )
			System.out.printf( " %2d[%2d] ", distWho[i][j], distVal[i][j] );
		System.out.printf( "\n" );
	}
	*/
}
	catch (IOException ee) {}
}


static void sortDists() {
	long [] sortArr  = new long [Nsites-1];
	final long ff = 0x100000000L;

	for( int i = 0; i < Nsites; i++ ){
		for( int j = 1; j < Nsites; j++ )
			sortArr[j-1] = distVal[i][j] * ff + distWho[i][j];
		Arrays.sort( sortArr );
		for( int j = 1; j < Nsites; j++ ){
			distVal[i][j] =  (int)(sortArr[j-1] / ff);
			distWho[i][j] =  (int)(sortArr[j-1] % ff);
		}
	}
}

}