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

const int N = 100005;
const int LIM = 15;

struct node {
    int x, y, c; 
} a[N]; 
int ans = 1e9;

int qwq[N], len, n; 
 
int calc(int L, int R) { 
//    printf("calc %d %d\n", L, R); 
    len = 0; 
    for (int i = L; i <= R; i++) {
        qwq[++len] = a[i].y * 3 + a[i].c; 
    } 
    sort(qwq + 1, qwq + len + 1);
    int las[3];
    memset(las, -0x3f, sizeof(las));
    int ret = 1e9; 
    for (int i = 1; i <= len; i++) {
        int u = qwq[i];
        las[u % 3] = u / 3;
        int t = *min_element(las, las + 3);
        ret = min(ret, u / 3 - t);
    } 
//    printf("get result = %d\n", ret); 
    return ret; 
} 

void solve() {
    sort(a + 1, a + n + 1, [&](node x, node y) { return x.x < y.x; });
    
    static int back[N];
    for (int i = 1; i <= n; i++) {
        if (a[i].x == a[i - 1].x) back[i] = back[i - 1];
        else back[i] = i; 
    } 
    
    int las[3];
    memset(las, -0x3f, sizeof(las)); 
    for (int i = 1; i <= n; i++) {
        if (clock() / 1. / CLOCKS_PER_SEC > 4.90) {
            printf("%d\n", ans);
            exit(0); 
        } 
        las[a[i].c] = i;
        int t = *min_element(las, las + 3);
        if (t <= 0 || a[i].x - a[t].x >= ans || a[i].x == a[i + 1].x) continue;
        int down = max(1, t - LIM); 
        int times = LIM, j = t; 
        while (times-- && j) {
            if (clock() / 1. / CLOCKS_PER_SEC > 4.90) {
                printf("%d\n", ans);
                exit(0); 
            } 
            if (a[i].x - a[j].x >= ans) break;
            j = back[j]; 
            ans = min(ans, a[i].x - a[j].x + calc(j, i));
            j--; 
        } 
    } 
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        scanf("%d", &a[i].c); 
    }
    solve();
    for (int i = 1; i <= n; i++)
        swap(a[i].x, a[i].y);
    solve();
    printf("%d\n", 2 * ans);
    return 0; 
}