#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#define ll long long

using namespace std;

struct info
{
    ll bit;
    int place;
};


long long MOD = 1000000007;

ll dp[1LL<<17][17];
int N;
ll dist[17][17];

void bfs(){
    queue<info> que;

    que.push({0,0});

    while(!(que.empty())){
        ll bit=que.front().bit;
        int place=que.front().place;
        que.pop();

        for(int i=0; i<N; i++){
            ll tmp=1<<i;
            if(!(bit&tmp)){
                ll nbit=bit|tmp;
                if(dp[nbit][i]==MOD*MOD){
                    que.push({nbit,i});
                }
                dp[nbit][i]=min(dp[nbit][i],dp[bit][place]+dist[place][i]);
            }
        }
    }
}

ll XYZ[17][3];

int main(){
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<3; j++){
            cin >> XYZ[i][j];
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            dist[i][j]=abs(XYZ[j][0]-XYZ[i][0])+abs(XYZ[j][1]-XYZ[i][1])+max(0LL,XYZ[j][2]-XYZ[i][2]);
        }
    }


    for(int i=(1<<N)-1; i>=0; i--){
        for(int j=0; j<N; j++){
            dp[i][j]=MOD*MOD;
        }
    }
    dp[0][0]=0;

    bfs();
    /*
    for(int i=0; i<(1<<N); i++){
        for(int j=0; j<N; j++){
            cout << dp[i][j] << ' ';
        }
        cout << endl;
    }*/
    cout << dp[(1<<N)-1][0] << endl;
}
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define ll long long
#define pb push_back
#define Mid ((L+R)/2)
#define pi pair<int,int>
#define pii pair<pi,int>
#define deb(x) cout<<#x<<"="<<x<<endl
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int n;
ll dp[17][1<<18],a[20],b[20],c[20];
ll Solve(int i,int msk)
{
    if(msk+1==(1<<n) && !i)
        return 0;
    ll &ret=dp[i][msk];
    if(ret+1) return ret;
    ret=1e18;
    for(int j=0;j<n;j++)
        ret=min(ret,Solve(j,msk|(1<<j))+abs(a[i]-a[j])+abs(b[i]-b[j])+max(0LL,c[j]-c[i]));
    return ret;
}
int main()
{
    go;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i]>>b[i]>>c[i];
    memset(dp,-1,sizeof dp);
    cout<<Solve(0,0);
    return 0;
}
