/*
   Pokemon Go Go
   Bruce Elenbogen
*/

#include <vector>
#include <climits>
#include <queue>
#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;
};

struct SearchNode {
	vector<int> seq;
	int distSoFar;
	int bound;
	bool operator<(const SearchNode &  rhs) const {
		return bound > rhs.bound;
	}
};

vector<vector<int> >  setUpAdj(vector<Stop> locations) {
	vector<vector<int> > tempAdj(locations.size());
	for (int i = 0; i < locations.size(); i++)
		tempAdj[i].resize(locations.size());
        /*cout<<"Adjaceny Matrix\n";*/
	for (int i = 0; i < locations.size(); i++) {
		for (int j = 0; j < locations.size(); j++) {
			tempAdj[i][j] = abs(locations[i].row - locations[j].row)
				+ abs(locations[i].col - locations[j].col);
			//cout << tempAdj[i][j] << " ";
		}
		//cout << endl;
	}

	return tempAdj;
}

vector<int> minValues(const vector<vector<int> > & adjMat) {
	vector<int> mins(adjMat.size(), INT_MAX);
	for (unsigned int i = 0; i < adjMat.size(); i++) {
		for (unsigned int j = 0; j < adjMat.size(); j++)
			if (i != j && adjMat[i][j] < mins[i])
				mins[i] = adjMat[i][j];
	}
	return mins;
}

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 ComputeBound(vector<int> seq, vector<int> minDists, vector<int> permute, int bndSoFar) {
	for (int i = 1; i < permute.size(); i++)
		if (findIndex(permute[i], seq) < 0 )
			bndSoFar += minDists[permute[i]];
	return bndSoFar;
}

int branchNBound(const vector<vector<int> > & adjMat, const vector<Stop> & locations,
	const vector<int> & permute, const vector<int> minDists) {
	SearchNode node;
	SearchNode newNode;
	priority_queue<SearchNode> que;

	node.seq.push_back(0);
	node.distSoFar = 0;
	node.bound = ComputeBound(node.seq, minDists, permute, 0) + minDists[0];
	que.push(node);
	while (!que.empty()) {
		node = que.top();
		que.pop();
		if (node.seq.size() > permute.size() ) {
			return node.distSoFar;
		}
		else
                if (node.seq.size() == permute.size()) {
			node.seq.push_back(0);
			node.distSoFar += (adjMat[node.seq[node.seq.size() - 2]][0]);
                        node.bound = node.distSoFar  ;
                        //return node.distSoFar;
			que.push(node);
		}
		else {
			for (int i = 1; i < permute.size(); i++) {
				if (findIndex(permute[i], node.seq) < 0) {
					newNode.seq = node.seq;
					newNode.seq.push_back(permute[i]);
					newNode.distSoFar = node.distSoFar + (adjMat[permute[i]][node.seq[node.seq.size() - 1]]);
					newNode.bound = ComputeBound(newNode.seq, minDists, permute, newNode.distSoFar)
						+ minDists[0];
					que.push(newNode);
				}
			}//for

		}//else
	}//while
}

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

	cin>> numStops;
	locations.resize(numStops+1);
	adjMat.resize(numStops + 1);
	for (int i = 0; i < numStops+1; i++)
		adjMat[i].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 );
	adjMat = setUpAdj(locations);
	minDist = minValues(adjMat);
	//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;
	bestDist = computeTotalDist(locations, permute);
	do {
		seq.push_back(0);
		dist = branchNBound(adjMat, locations, permute, minDist);
		if (dist < bestDist)
			bestDist = dist;
	} while (nextPermute(permute, uniqueNames));
	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


24
1 2 a
2 3 b
3 4 c
4 5 d
-1 2 e
-2 3 f
-3 4 g
-4 5 h
1 -2 i
2 -3 j
3 -4 k
4 -5 l
-1 -2 m
-2 -3 n
-3 -4 o
-4 -5 p
5 6 q
-5 6 r
-5 -6 s
5 -6 t
6 7 u
-6 -7 v
-6 7 w
6 -7 x


*/