#include <bits/stdc++.h>
using namespace std;

struct point{
	int x,y,col,id;
	point turn90(){
		return (point){-y,x,col,id};
	}
};

const int N=100000;
int mnx[N+50],mny[N+50];
int x[N+50],y[N+50],col[N+50];
int n;

int solve(vector<point> &a){
	for (int i=1;i<=n;i++) mnx[i]=mny[i]=0;
	
	{
		sort(a.begin(),a.end(),
			[](const point &p,const point &q){
				return (p.x==q.x)?(p.y==q.y?p.col<q.col:p.y<q.y):(p.x<q.x);
			}
		);
		set< pair<int,int> > s;
		s.insert(make_pair(-100000000,-100000000));
		for (auto e:a){
			if (e.col==0) s.insert(make_pair(e.y,e.x));
			if (e.col==2){
				auto it=s.upper_bound(make_pair(e.y,e.x));
				it--;
				auto tmp=(*it);
				mnx[e.id]=max(mnx[e.id],e.x-tmp.second);
				mny[e.id]=max(mny[e.id],e.y-tmp.first);
			}
		}
	}
	{
		sort(a.begin(),a.end(),
			[](const point &p,const point &q){
				return (p.y==q.y)?(p.x==q.x?p.col<q.col:p.x<q.x):(p.y<q.y);
			}
		);
		set< pair<int,int> > s;
		s.insert(make_pair(-100000000,-100000000));
		for (auto e:a){
			if (e.col==1) s.insert(make_pair(e.x,e.y));
			if (e.col==2){
				auto it=s.upper_bound(make_pair(e.x,e.y));
				it--;
				auto tmp=(*it);
				mnx[e.id]=max(mnx[e.id],e.x-tmp.first);
				mny[e.id]=max(mny[e.id],e.y-tmp.second);
			}
		}
	}
	
	int ans=2e9;
	for (auto e:a) if (e.col==2) ans=min(ans,2*(mnx[e.id]+mny[e.id]));
	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i=1;i<=n;i++) cin >> x[i] >> y[i] >> col[i];
	vector<int> p(3);
	for (int i=0;i<=2;i++) p[i]=i;
	int ans=2e9;
	do{
		vector<point> a;
		for (int i=1;i<=n;i++) a.emplace_back(x[i],y[i],p[col[i]],i);
		for (int i=1;i<=4;i++){
			for (auto &e:a) e=e.turn90();
			ans=min(ans,solve(a));	
		}
	}while(next_permutation(p.begin(),p.end()));
	cout << ans << "\n";
	return 0;	
}