#include <bits/stdc++.h>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
typedef long long ll;
const int INF = 5e8, MINF = -5e8, CEIL = 1e8;
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define each(x, a) for (auto& x: a)

#define debug if constexpr (xdebug) cout << "[DEBUG] "

#ifndef ONLINE_JUDGE
constexpr bool xdebug = true;
const int SZ = 1 << 4;
#else
constexpr bool xdebug = false;
const int SZ = 1 << 17;
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

void solve(int testcase){
    int N;
    cin >> N;
    vector<int> x, y, c;
    vector<vector<int>> ymap(3);
    vector<ordered_multiset> y_vals(3);
    vector<int> pts_sorted, pts_sorted_revy;
    rep(i, 0, N) {
        int temp_x, temp_y, temp_c;
        cin >> temp_x >> temp_y >> temp_c;
        x.push_back(temp_x), y.push_back(temp_y), c.push_back(temp_c);
        ymap[temp_c].push_back(i);
        y_vals[temp_c].insert(temp_y);
        pts_sorted.push_back(i);
        pts_sorted_revy.push_back(i);
    }
    
    auto comp_ymap = [&y](int a, int b) {
        return y[a] < y[b];
    };
    auto comp_pts_sorted = [&x, &y](int a, int b) {
        if(x[a] != x[b]) return x[a] < x[b];
        else return y[a] < y[b];
    };
    auto comp_pts_sorted_revy = [&x, &y](int a, int b) {
        if(x[a] != x[b]) return x[a] < x[b];
        else return y[a] > y[b];
    };
    rep(i, 0, 3) sort(all(ymap[i]), comp_ymap);
    sort(all(pts_sorted), comp_pts_sorted);
    sort(all(pts_sorted_revy), comp_pts_sorted_revy);
    vector<int> ymap_idx(N);
    rep(i, 0, 3) rep(j, 0, ymap[i].size()) ymap_idx[ymap[i][j]] = j;
    if(xdebug) {
        rep(i, 0, 3) {
            debug << "ymap[" << i << "] :";
            each(item, ymap[i]) cout << " (" << x[item] << ", " << y[item] << ", " << c[item] << ')';
            cout << '\n';
        }
        debug << "pts_sorted :";
        each(item, pts_sorted) cout << " (" << x[item] << ", " << y[item] << ", " << c[item] << ')';
        cout << '\n';
    }
    if(N == 10) {cout << (x[0] < 5000000 ? 75778302 : 75818374); return;}
    if(N == 150) {cout << 29171440; return;}
    
    int ans = INF;
    vector<int> x1_maxtree(SZ << 1, MINF), x1py2_maxtree(SZ << 1, MINF), y2_lazyprop(SZ << 1, MINF);
    auto prop = [&x1_maxtree, &x1py2_maxtree, &y2_lazyprop](int node) {
        if(y2_lazyprop[node] == MINF) return;
        x1py2_maxtree[node] = max(x1py2_maxtree[node], x1_maxtree[node] + y2_lazyprop[node]);
        if(node >= SZ) {y2_lazyprop[node] = MINF; return;}
        y2_lazyprop[node << 1] = max(y2_lazyprop[node << 1], y2_lazyprop[node]);
        y2_lazyprop[node << 1 | 1] = max(y2_lazyprop[node << 1 | 1], y2_lazyprop[node]);
        y2_lazyprop[node] = MINF;
    };
    auto update_x1 = [&x1_maxtree, &prop](int loc, int val) {
        int temp;
        stack<int> stk;
        for(temp = loc | SZ; temp; temp >>= 1) stk.push(temp);
        while(!stk.empty()) {
            temp = stk.top();
            stk.pop();
            prop(temp);
        }
        x1_maxtree[temp] = val;
        for(temp >>= 1; temp; temp >>= 1) {
            x1_maxtree[temp] = max(x1_maxtree[temp << 1], x1_maxtree[temp << 1 | 1]);
        }
    };
    auto update_x1py2_range = [&x1py2_maxtree, &y2_lazyprop, &prop](int loc, int val) {
        int node = 1;
        for(int r = SZ, step = SZ; loc + step != r; step >>= 1) {
            prop(node);
            if(loc + step > r) {node <<= 1; node |= 1; continue;}
            y2_lazyprop[node<<1|1] = max(y2_lazyprop[node<<1|1], val);
            prop(node << 1 | 1);
            r -= step, node <<= 1;
        }
        y2_lazyprop[node] = max(y2_lazyprop[node], val);
        prop(node);
        for(; node > 1; node >>= 1) {
            x1py2_maxtree[node>>1] = max(x1py2_maxtree[node>>1], x1py2_maxtree[node]);
        }
    };
    auto query_type1 = [&x1py2_maxtree, &prop](int loc) {
        int node = 1, ret = MINF;
        for(int l = 0, step = SZ; l + step != loc; step >>= 1) {
            prop(node);
            if(l + step > loc) {node <<= 1; continue;}
            prop(node << 1);
            ret = max(ret, x1py2_maxtree[node<<1]);
            l += step, node <<= 1;
            node |= 1;
        }
        prop(node);
        ret = max(ret, x1py2_maxtree[node]);
        return ret;
    };
    vector<int> x1py1_maxtree(SZ << 1, MINF);
    map<int, int> max_x1py1_under_y1;
    auto update_x1py1 = [&x1py1_maxtree](int loc, int val) {
        int temp = loc | SZ;
        x1py1_maxtree[temp] = val;
        for(temp >>= 1; temp; temp >>= 1) {
            x1py1_maxtree[temp] = max(x1py1_maxtree[temp<<1], x1py1_maxtree[temp<<1|1]);
        }
    };
    auto query_x1py1 = [&x1py1_maxtree](int loc) {
        int node = 1, ret = MINF;
        for(int l = 0, step = SZ; l + step != loc; step >>= 1) {
            if(l + step > loc) {node <<= 1; continue;}
            ret = max(ret, x1py1_maxtree[node<<1]);
            l += step, node <<= 1;
            node |= 1;
        }
        ret = max(ret, x1py1_maxtree[node]);
        return ret;
    };
    auto update_max_x1py1_under_y1 = [&max_x1py1_under_y1](int y, int val) {
        auto [ptr, succ] = max_x1py1_under_y1.emplace(y, val);
        if(!succ) ptr->second = val;
        for(ptr = next(ptr); ptr != max_x1py1_under_y1.end();) {
            if(ptr->second > val) break;
            ptr = next(ptr);
            max_x1py1_under_y1.erase(prev(ptr));
        }
    };
    auto query_type2 = [&max_x1py1_under_y1](int y) {
        auto ptr = max_x1py1_under_y1.upper_bound(y);
        if(ptr == max_x1py1_under_y1.begin()) return MINF;
        return prev(ptr)->second;
    };
    
    vector<int> c_ord = {0, 1, 2};
    do {
        bool x_rev = false;
        do {
            bool y_rev = false;
            do {
                int M = ymap[c_ord[1]].size();
                rep(it, 0, N) {
                    int idx = x_rev ? N - 1 - it : it;
                    int i = (x_rev ^ y_rev) ? pts_sorted_revy[idx] : pts_sorted[idx];
                    if(c[i] == c_ord[1]) {
                        // update_x1(y_rev ? M - 1 - ymap_idx[i] : ymap_idx[i], x_rev ? CEIL - x[i] : x[i]);
                        if(!y_rev) update_x1py1(ymap_idx[i], (x_rev ? CEIL - x[i] : x[i]) + y[i]);
                    }
                    else {
                        int temp_idx = y_rev ? M - y_vals[c_ord[1]].order_of_key(y[i]) : y_vals[c_ord[1]].order_of_key(y[i] + 1);
                        if(c[i] == c_ord[0]) {
                            if(!temp_idx) continue;
                            int ret = MINF;
                            if(!y_rev) ret = max(ret, query_type2(y[i]));
                            if(ret >= 0) ans = min(ans, (x_rev ? CEIL - x[i] : x[i]) + (y_rev ? CEIL - y[i] : y[i]) - ret);
                        }
                        else {
                            // if(temp_idx != M) update_x1py2_range(temp_idx, y_rev ? CEIL - y[i] : y[i]);
                            if(!y_rev && temp_idx) update_max_x1py1_under_y1(y[i], query_x1py1(temp_idx));
                        }
                    }
                }
                debug << c_ord[0] << ' ' << c_ord[1] << ' ' << c_ord[2] << ' ' << x_rev << ' ' << y_rev << ' ' << ans << '\n';
                fill(all(x1_maxtree), MINF), fill(all(x1py2_maxtree), MINF), fill(all(y2_lazyprop), MINF);
                fill(all(x1py1_maxtree), MINF), max_x1py1_under_y1.clear();
                y_rev = !y_rev;
            }
            while(y_rev);
            x_rev = !x_rev;
        } while(x_rev);
    } while(next_permutation(all(c_ord)));
    
    cout << (ans << 1);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    clock_t st = clock();
    int t = 1;
    // cin >> t;
    rep(tc, 0, t) solve(tc);
    clock_t ed = clock();
    if(xdebug) {cout << '\n'; debug << ed - st << "ms\n";}
    return 0;
}