#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<stack>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll N;
ll dp[18][(1<<18)];
ll x[20],y[20],z[20];
ll d[20][20];
ll Cost(ll now,ll next){
    return abs(x[next]-x[now])+abs(y[next]-y[now])+max(0ll,z[next]-z[now]);
}
int main(){
    cin>>N;
    for(ll i=0;i<N;i++){
        cin>>x[i]>>y[i]>>z[i];
    }
    for(ll i=0;i<N;i++){
        for(ll j=0;j<N;j++){
            d[i][j] = Cost(i,j);
        }
    }
    for(ll i=0;i<N;i++){
        for(ll j=0;j<(1<<N);j++){
            dp[i][j]=INF;
        }
    }
    dp[0][1]=0;
    for(ll state=1;state<(1<<N);state+=2){
        for(ll now=0;now<N;now++){
            if(dp[now][state]==INF)continue;
            for(ll next=0;next<N;next++){
                if(next==now)continue;
                if((1<<next) & state)continue;
                dp[next][state | (1<<next)] = min(dp[next][state | (1<<next)], dp[now][state]+d[now][next]);
            }
        }
    }
    ll ans=INF;
    for(ll i=1;i<N;i++){
        ans=min(ans,dp[i][(1<<N)-1]+d[i][0]);
    }
    cout<<ans<<endl;

    return 0;
}
#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]));
            }
        }
    }
    cout << dp[(1<<n)-1][0] << endl;
}
