/*
   Pokemon Go Go
   Bruce Elenbogen
*/

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int abs(int n){
	if (n>=0) return n;
	return -n;
}

struct Stop{
	int row;
	int col;
	string name;
};

int computeTotalDist(const vector<Stop> & location, const vector<int> & order){
	int totalDist = 0;
	int size = order.size();
	for (int i = 0; i < size-1; i++)
	  totalDist += abs(location[order[i+1]].row - location[order[i]].row)+
	                abs(location[order[i+1]].col - location[order[i]].col);
	totalDist += abs(location[order[0]].row - location[order[size-1]].row)+
	                abs(location[order[0]].col - location[order[size-1]].col);
	return totalDist;
}

int findIndex(int index, const vector<int> & uniqueNames){
	for (int i = 0; i < uniqueNames.size(); i++)
	if (index == uniqueNames[i])
		return i;
	return -1;
}

bool nextPermute(vector<int> & lastPermute, vector<vector<int> > &uniqueNames ){
	bool done = false;
	int index;
	for(int i = 1 ; i < lastPermute.size()&& !done;i++){
		index = findIndex(lastPermute[i], uniqueNames[i]);
		if (index < 0)
			system("pause");
	  if (index <uniqueNames[i].size()-1 ){
		  lastPermute[i]= uniqueNames[i][++index];
		  return true;
	  }
	  else if (index == uniqueNames[i].size()-1)
	    {
	       lastPermute[i]= uniqueNames[i][0];
		}
	}
	 return done;
}

void setUpUniqueNames(const vector<Stop> & locations, vector<vector<int> > & indexUniqueNames ){
	vector<int> temp(1,0);
	bool placed;
	string name;
	indexUniqueNames.push_back(temp);
	for (int i = 1; i < locations.size(); i++){
		name = locations[i].name;
		placed= false;
		 for (int j = 0; j < indexUniqueNames.size()&& !placed; j++)
		   if (name == locations[indexUniqueNames[j][0]].name){
			 placed = true;
			 indexUniqueNames[j].push_back(i);
		   }
		if (!placed){
			temp[0]=i;
			indexUniqueNames.push_back(temp);
		}
	  }
}

int main(){
	int numStops;
	vector<Stop> locations;
	vector<int> permute;
	vector<int> temp;
	vector<int> bestOrder;
	vector<vector<int> > uniqueNames;
	int bestDist;
	int dist;

	cin>> numStops;
	locations.resize(numStops+1);
    //permute.resize(numStops+1);
    //bestOrder.resize(numStops+1);

	locations[0].row = 0;
	locations[0].col = 0;
	locations[0].name="";
	for (int i = 1; i < numStops+1; i++)
	  cin>> locations[i].row>>locations[i].col>>locations[i].name;
	setUpUniqueNames(locations,uniqueNames );
	//cout<<"after set "<<uniqueNames.size()<<endl;
	for (int i = 0; i < uniqueNames.size(); i++){
       permute.push_back(uniqueNames[i][0]);
      //cout<<permute[i];
	}
	//cout << endl;
	bestOrder = permute;
	bestDist = computeTotalDist(locations, permute);
	do {
		//for (unsigned int i = 1; i < permute.size();i++)
		//   cout<<permute[i]<<" ";
	   //cout<<endl;
		temp = permute;
		sort(temp.begin(), temp.end());
		do{
	    dist = computeTotalDist(locations, temp);
	    if (dist< bestDist){
		bestOrder = temp;
		bestDist = dist;
		}
	 } while (next_permutation(temp.begin() + 1, temp.end()));
	}while(nextPermute(permute, uniqueNames));

	/* for (unsigned int i = 1; i < bestOrder.size(); i++)
	   cout<<bestOrder[i] <<" ";
         */
	cout<<bestDist<<endl;

	return 0;
}

/*

5
5 9 Eevee
50 50 Flareon
1 1 Flareon
1 8 Joteon
2 8 Umbreon


8
1 2 a
2 3 b
3 4 c
4 5 a
5 6 b
6 7 c
7 8 a
8 9 b

*/