#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define eps (double)(1e-9)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

ll cost(ll a, ll b, ll c, ll p, ll q, ll r){
    return abs(a-p) + abs(b-q) + max(0LL, r-c);
}

int main() {
    int n;
    cin >> n;
    vector<ll> x(n), y(n), z(n);
    rep(i, n)cin >> x[i] >> y[i] >> z[i];
    vector<vector<ll>> dp(1<<n, vector<ll>(n, inf));
    dp[0][0] = 0;
    rep(i, (1<<n)-1){
        rep(j, n){
            if(i & (1<<j) == 0)continue;
            rep(k, n){
                chmin(dp[i|(1<<k)][k], dp[i][j] + cost(x[j],y[j],z[j],x[k],y[k],z[k]));
            }
        }
    }
    vector<vector<ll>> mn(n, vector<ll>(n, inf));
    rep(i, n)rep(j, n)mn[i][j] = cost(x[i],y[i],z[i],x[j],y[j],z[j]);
    rep(k, n)rep(i, n)rep(j, n){
        chmin(mn[i][j], mn[i][k] + mn[k][j]);
    }
    ll ans = inf;
    rep(i, n)chmin(ans, dp[(1<<n)-1][i] + mn[i][0]);
    cout << ans << endl;
}

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define N               25
#define ff              first
#define ss              second
#define ll              long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<ll,ll>
#define vi              vector<ll>
#define mii             map<ll,ll>
#define pq_max          priority_queue<ll>
#define pq_min          priority_queue<ll,vi,greater<ll> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define inp(arr,n)      for(ll x=0;x<n;x++) cin>>arr[x];
#define w(x)            ll x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void fio(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

ll n, done;
vector<vi> xyz;
ll dist[N][N], dp[1<<20][20];

ll f(ll mask, ll pos){
    if(mask == done) return dist[pos][0];

    if(dp[mask][pos] != -1) return dp[mask][pos];

    ll ans = inf;
    for(ll x=0;x<n;x++){
        if(! (mask & (1 << x))){
            ans = min(ans, f(mask|(1<<x), x) + dist[pos][x]);
        }
    }

    return dp[mask][pos] = ans;
}

int main(){
    fio();

    cin>>n;
    done = (1 << n) - 1;
    xyz.resize(n, vi(3));
    memset(dp, -1, sizeof dp);
    for(ll x=0;x<n;x++){
        cin>>xyz[x][0]>>xyz[x][1]>>xyz[x][2];
    }

    for(ll x=0;x<n;x++){
        for(ll y=0;y<n;y++){
            ll d = abs(xyz[x][0] - xyz[y][0]) + abs(xyz[x][1] - xyz[y][1]) + max(0ll, xyz[y][2] - xyz[x][2]);
            dist[x][y] = d;
        }
    }

    cout<<f(1, 0);

    return 0;
}