#include<bits/stdc++.h>
using namespace std;
typedef struct Point {
	int x,y,z; 
}Point; 
int f(Point a ,Point b){
	int v1 = abs(a.x - b.x);
	int v2 = abs(a.y - b.y);
	int v3 = max(0,b.z - a.z);
	return v1+v2+v3;
}
int main(){
	int n; cin>>n;
	Point a[n];
	int x,y,z;
	for(int i=0;i<n;i++) { cin>>x>>y>>z; a[i]={x,y,z}; }
	int dp[1<<n][n];
	const int INF = 0x3f3f3f3f;
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			dp[i][j]=INF;
		}
	}
	dp[1][0]=0;
	for(int i=2;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			if(i&(1<<j)){
			int tgt = i^(1<<j);
			for(int k=0;k<n;k++){
				dp[i][j]=min(dp[i][j],dp[tgt][k]+f(a[k],a[j]));
			}
		}
	}
}
int ans = INF;
for(int i=0;i<n;i++){ ans = min(ans,dp[(1<<n)-1][i]+f(a[i],a[0])); }
cout<<ans<<'\n';
return 0;
}

//---------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <sstream>
#include <numeric>
#include <cassert>
//---------------------------------------------------------------
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define SIZE 100005
#define INF 1e18
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define vec vector
using pint = pair<int,int>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
//---------------------------------------------------------------
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const double pi = acos(-1);
//---------------------------------------------------------------

//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓


int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    ll n;
    cin>>n;
    vll x(n),y(n),z(n);
    rep(i,n)cin>>x[i]>>y[i]>>z[i];

    auto dis = [&](ll v, ll nv) {
        ll add = abs(x[v]-x[nv])+abs(y[v]-y[nv])+max(0ll,z[nv]-z[v]);
        return add;
    };

    vec<vll> dp(1<<n, vll(n+1,INF));
    dp[1][0] = 0;
    rep(bit,1<<n){
        rep(v,n){
            if(!(bit&(1<<v))) continue;//ｖが探索済みでないならスルー
            rep(nv,n){
                if(bit & (1<<n)) continue;//nvが探索済みならスルー
                int nbit = bit | (1<<nv); //bitに探索済みのものを入れる
                chmin(dp[nbit][nv],dp[bit][v]+dis(v,nv));
            }
        }
    }

    ll res=INF;
    rep(v,n){
        chmin(res,dp[(1<<n)-1][v]+dis(v,0));
    }

    cout<<res<<endl;
}
