#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a, I = b; i <= I; ++i)
#define per(i, a, b) for (int i = a, I = b; i >= I; --i)
using namespace std;
using i64 = long long;
using i128 = __int128_t;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }

const int N = 100005;
int n, xx[N], yy[N], px[N], py[N], x[N], y[N], c[N], cc[N], cx, cy, ans = 1e9;
vector<int> e[N][3];

void prework() {
    rep(i, 1, n) {
        swap(xx[i], yy[i]);
        yy[i] = 1e8 - yy[i];
        px[i] = xx[i], py[i] = yy[i];
    }
    sort(px + 1, px + n + 1), cx = unique(px + 1, px + n + 1) - px - 1;
    sort(py + 1, py + n + 1), cy = unique(py + 1, py + n + 1) - py - 1;
    rep(i, 1, n) {
        x[i] = lower_bound(px + 1, px + cx + 1, xx[i]) - px;
        y[i] = lower_bound(py + 1, py + cy + 1, yy[i]) - py;
    }
}

namespace case1 {
    struct BIT {
        int c[N];
        void init() { memset(c, 0x3f, sizeof c); }
        void modify(int p, int x, bool type = false) {
            if (type) p = cy - p + 1;
            for (; p <= cy; p += p & -p) down(c[p], x);
        }
        int query(int p, bool type = false) {
            if (type) p = cy - p + 1;
            int res = 0x3f3f3f3f;
            for (; p; p -= p & -p) down(res, c[p]);
            return res;
        }
    } tr;
    int ans[N];

    void solve() {
        memset(ans, 0, sizeof ans);
        {
            tr.init();
            rep(i, 1, cx) {
                for (auto id : e[i][0]) tr.modify(y[id], -(px[x[id]] + py[y[id]]));
                for (auto id : e[i][1]) ans[id] += tr.query(y[id]);
            }
        }        
        {
            tr.init();
            per(i, cx, 1) {
                for (auto id : e[i][2]) tr.modify(y[id], px[x[id]] + py[y[id]], true);
                for (auto id : e[i][1]) ans[id] += tr.query(y[id], true);
            }
        }
        rep(i, 1, n) if (c[i] == 1) down(::ans, ans[i]);
    }
}

namespace case2 {
    const int M = 1 << 18 | 5;
    struct node {
        int a, b, c;
        node(int a = 1e9, int b = 1e9, int c = 1e9) : a(a), b(b), c(c) {}
        node operator+(const node &rhs) const {
            node res;
            res.a = min(a, rhs.a);
            res.b = min(b, rhs.b);
            res.c = min(min(c, rhs.c), a + rhs.b);
            return res;
        }
        bool operator==(const node &rhs) const { return a == rhs.a && b == rhs.b && c == rhs.c; }
    } lazy[M];

    void build() {
        fill(lazy, lazy + M, node());
    }
    void tag(int p, const node &x) {
        lazy[p] = lazy[p] + x;
    }
    void push_down(int p) {
        if (lazy[p] == node()) return;
        tag(p << 1, lazy[p]);
        tag(p << 1 | 1, lazy[p]);
        lazy[p] = node();
    }
    void modify(int p, int l, int r, int ll, int rr, const node &x) {
        if (l >= ll && r <= rr) return tag(p, x);
        int mid = (l + r) >> 1;
        push_down(p);
        if (mid >= ll) modify(p << 1, l, mid, ll, rr, x);
        if (mid < rr) modify(p << 1 | 1, mid + 1, r, ll, rr, x);
    }
    int query(int p, int l, int r, int pos) {
        if (l == r) return lazy[p].c;
        int mid = (l + r) >> 1;
        push_down(p);
        if (mid >= pos) return query(p << 1, l, mid, pos);
        else return query(p << 1 | 1, mid + 1, r, pos);
    }

    void solve() {
        build();
        per(i, cx, 1) {
            for (auto id : e[i][2]) modify(1, 1, cy, 1, y[id], node(x[id] + y[id], 1e9, 1e9));
            for (auto id : e[i][1]) modify(1, 1, cy, y[id], cy, node(1e9, -y[id], 1e9));
            for (auto id : e[i][0]) down(ans, query(1, 1, cy, y[id]) - x[id]);
        }
    }
}

int main() {
   // freopen("1.in", "r", stdin);
	ios::sync_with_stdio(0), cin.tie(0);

    cin >> n;
    rep(i, 1, n) cin >> xx[i] >> yy[i] >> cc[i];

    rep(t, 0, 3) {    
        prework();
        static int perm[3];
        iota(perm, perm + 3, 0);
        do {
            rep(i, 1, n) c[i] = perm[cc[i]];
            rep(i, 1, cx) rep(j, 0, 2) e[i][j].clear();
            rep(i, 1, n) e[x[i]][c[i]].push_back(i);
            if (t < 2) case1::solve();
            case2::solve();
        } while (next_permutation(perm, perm + 3));
    }

    cout << ans * 2 << "\n";

	return 0;
}