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

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef pair<int,int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

void Main(){
    int N; cin >> N;
    VL X(N), Y(N), Z(N); REP(i,N) cin >> X[i] >> Y[i] >> Z[i];
    ll d[N][N];
    REP(i,N)REP(j,N){
        ll x = abs(X[i]-X[j]), y = abs(Y[i]-Y[j]), z = max((ll)0, Z[j]-Z[i]);
        d[i][j] = x + y + z;
    }
    REP(k,N)REP(i,N)REP(j,N) chmin(d[i][j], d[i][k]+d[k][j]);

    VI p(1<<N,0);
    REP(i,1<<N){
        int j = i<<1, k = (i<<1)+1;
        if(j<(1<<N)){
            p[j] = p[i];
        }
        if(k<(1<<N)){
            p[k] = p[i]+1;
        }
    }

    ll dp[1<<N][N]; REP(i,1<<N)REP(j,N) dp[i][j] = LINF;
    dp[0][0] = 0;
    REP(i,1<<N){REP(j,N){
        if(dp[i][j]==LINF) continue;
        REP(k,N){
            if((i>>k)&1) continue;
            int nxt = i | (1<<k);
            chmin(dp[nxt][k], dp[i][j]+d[j][k]);
        }
    }
    }

    ll ans = dp[(1<<N)-1][0];
    cout << ans << en;
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
typedef pair<string,int> psi;
typedef pair<int,string> pis;
typedef array<int,2> aii;
typedef array<int,3> aiii;
typedef array<int,4> aiiii;
typedef unsigned long long ull;
typedef long long int ll;
typedef array<ll,2> all;
typedef array<ll,3> alll;
typedef array<ll,4> allll;

#define pb push_back
#define ff first
#define ss second
#define MAX 300005
#define MOD 1000000007
#define INF 1e9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int>adj[MAX];
int xMove[] = { 0,1,0,-1,1,1,-1,-1, 2, 2, -2, -2, 1, 1, -1, -1 };
int yMove[] = { 1,0,-1,0,1,-1,1,-1, 1, -1, 1, -1, 2, -2, 2, -2 };
vector<aiii> vec;
int dp[1<<17][17][2],n;

int solve(int mask, int last, int visited_repeated)
{
    if(mask==(1<<n)-1)
    {
        return abs(vec[0][0]-vec[last][0])+abs(vec[0][1]-vec[last][1])+max(0,vec[0][2]-vec[last][2]);
    }

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

    int ans=INF;
    for(int i=0; i<n; i++)
    {
        if(!(mask&(1<<i)))
            ans=min(ans,abs(vec[i][0]-vec[last][0])+abs(vec[i][1]-vec[last][1])+max(0,vec[i][2]-vec[last][2])+solve(mask|(1<<i),i,0));
    }

    if(visited_repeated==0)
        for(int i=0; i<n; i++)
        {
            if(i!=last and (mask&(1<<i)))
                ans=min(ans,abs(vec[i][0]-vec[last][0])+abs(vec[i][1]-vec[last][1])+max(0,vec[i][2]-vec[last][2])+solve(mask,i,visited_repeated+1));
        }

    return dp[mask][last][visited_repeated]=ans;
}

int main()
{
    //freopen("input.in","r",stdin);
    //freopen("output.txt","w",stdout);
    cin.tie(0),cout.tie(0);
    ios_base::sync_with_stdio(0);
    cout.setf(ios::fixed);
    cout.precision(10);
    int TC=1;
    int m,k;

    //cin>>TC;
    for(int t1=1; t1<=TC; t1++)
    {
        cin>>n;
        vec.resize(n);
        for(auto &[a,b,c]: vec)
            cin>>a>>b>>c;
        memset(dp,-1,sizeof dp);

        cout<<solve(1,0,0)<<"\n";
    }

    return 0;
}
