/*
* Author: Geeza
*/

#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define pb push_back
#define fin(a, n) for(int i = a; i < n; i++)
#define fjn(a, n) for(int j = a; j < n; j++)
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

using namespace std;

const double PI = acos(-1);
const int N = 2e5+20;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353, inf = 1e6;

string di[] = {"D","L", "U", "R", "UL", "UR", "DL", "DR"};
int dx[] = {+1, +0, +0, -1, -1, -1, +1, +1};
int dy[] = {+0, -1, +1, +0, -1, +1, -1, +1};
char dc[] = {'D', 'L', 'R', 'U'};

int n;
vector<vector<ll>> dist;
ll dp[20][20];
vector<array<ll, 3>> v;

ll calc(int idx = 0, ll mask = 1ll) {
    if (mask == (1<<n)-1) {
        return dist[idx][0];
    }

    ll &ret = dp[idx][mask];
    if (~ret) return ret;
    ret = oo;
    for (int i = 0; i < n; i++) {
        if ((mask>>i)&1) continue;
        ret = min(ret, calc(i, mask|(1ll<<i))+dist[idx][i]);
    }
    return ret;
}

void solve() {
    cin >> n;
    v.assign(n, {0, 0, 0});
    fin(0, n) cin >> v[i][0] >> v[i][1] >> v[i][2];

    dist = vector<vector<ll>>(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            dist[i][j] = abs(v[i][0]-v[j][0]) + abs(v[i][1]-v[j][1]) + max(0ll, v[j][2]-v[i][2]);
        }
    }

    memset(dp, -1, sizeof dp);
    cout << calc() << "\n";
}

int main() {
    FAST;
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    int tt = 1; //cin >> tt;
    while(tt--){
        solve();
    }
    return 0;
}