#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+1e3+7;
struct Data{int ans[3];Data(int _a=1e18,int _b=1e18,int _c=1e18){ans[0]=_a,ans[1]=_b,ans[2]=_c;}};
    Data operator +(const Data&l,const Data&r){
        return Data{min(l.ans[0],r.ans[0]),min(l.ans[1],r.ans[1])
            ,min({l.ans[2],r.ans[2],l.ans[0]+r.ans[1]})};}
struct Seg_tr
{  
    struct T{int l,r,ls,rs;Data tag;}t[N*2+1];
    void pushdown(int x)
    {
        t[t[x].ls].tag=t[t[x].ls].tag+t[x].tag;
        t[t[x].rs].tag=t[t[x].rs].tag+t[x].tag;
        t[x].tag=Data();
    }
    int cnt=0;
    int build(int l,int r){
        int x=++cnt;t[x].l=l,t[x].r=r;for(int i=0;i<3;i++)t[x].tag.ans[i]=1e18;if(l==r)return x;
        int mid=(l+r)>>1;t[x].ls=build(l,mid);t[x].rs=build(mid+1,r);return x;}
    void change(int x,int l,int r,Data v){
        if(l<=t[x].l&&t[x].r<=r){t[x].tag=t[x].tag+v;return;}int mid=(t[x].l+t[x].r)>>1;
        pushdown(x);if(l<=mid)change(t[x].ls,l,r,v);if(r>mid)change(t[x].rs,l,r,v);}
    int qry(int x,int p){
        if(t[x].l==t[x].r)return t[x].tag.ans[2];int mid=(t[x].l+t[x].r)>>1;
        pushdown(x);return (p<=mid)?qry(t[x].ls,p):qry(t[x].rs,p);}
}A;
struct P{int x,y,c;};
struct BIT{
    int c[N],n;void init(int _n){for(int i=1;i<=_n;i++)c[i]=1e18;n=_n;}
    void add(int x,int v){while(x<=n){c[x]=min(c[x],v);x+=x&-x;}}
    int qry(int x){int ret=1e18;while(x){ret=min(ret,c[x]);x-=x&-x;}return ret;}
}T[2];
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);int rc[3];for(int i=0;i<3;i++)rc[i]=i;
    int n,ans=1e18;cin>>n;vector<P>op(n);for(auto&[x,y,c]:op)cin>>x>>y>>c;
    do{
        vector<P>p=op;for(auto&[x,y,c]:p)c=rc[c];
        for(int i=0;i<4;i++)
        {
            vector<int>Y;for(auto [x,y,c]:p)Y.push_back(y);sort(Y.begin(),Y.end());
            sort(p.begin(),p.end(),[&](const P &a,const P &b){return a.x^b.x?a.x<b.x:a.c<b.c;});
            {
                T[0].init(n);T[1].init(n);               
                for(auto [x,y,c]:p)
                {
                    int py=lower_bound(Y.begin(),Y.end(),y)-Y.begin()+1;
                    if(c==0)T[0].add(py,-x-y);
                    else if(c==1)T[1].add(py,T[0].qry(py));
                    else ans=min(ans,x+y+T[1].qry(py));
                }
            }            
            {
                A.cnt=0;A.build(1,n);
                for(auto [x,y,c]:p)
                {
                    int py=lower_bound(Y.begin(),Y.end(),y)-Y.begin()+1;
                    if(c==0)A.change(1,py,n,Data(-x-y,1e18,1e18));
                    else if(c==1)A.change(1,1,py,Data(1e18,y,1e18));
                    else ans=min(ans,x+A.qry(1,py));                    
                }
            }
            for(auto &[x,y,c]:p)swap(x,y),x=-x;           
        }
    }while(next_permutation(rc,rc+3));
    cout<<ans*2<<"\n";
}