#include <bits/stdc++.h>
#include <math.h>

using namespace std;

template<typename T>
long long modpow(const T n,const T p,const T mod);
template<typename T>
long long modinv(const T n,const T mod);
template<typename T>
bool chmax(T &a,const T &b);
template<typename T>
bool chmin(T &a,const T &b);

long long inf=1000000007;

int main(){
	long long n;
	cin>>n;
	vector<vector<long long>> tosi(n,vector<long long>(3));

	for(long long i=0;i<n;i++) cin>>tosi.at(i).at(0)>>tosi.at(i).at(1)>>tosi.at(i).at(2);
	vector<vector<long long>> dp(n,vector<long long>(modpow((long long)2,n,inf),inf));
	dp.at(0).at(0)=0;

	for(long long i=0;i<(1<<n);i++){
		bitset<18> bits=i;
		for(long long j=0;j<n;j++){
			if(!(i==0 && j==0) && bits.test(j)==false) continue;
			for(long long k=0;k<n;k++){
				if(bits.test(k)) continue;

				long long a=abs(tosi.at(j).at(0)-tosi.at(k).at(0));
				long long b=abs(tosi.at(j).at(1)-tosi.at(k).at(1));
				long long c=max((long long)0,tosi.at(k).at(2)-tosi.at(j).at(2));
				chmin(dp.at(k).at(i+modpow((long long)2,k,inf)),dp.at(j).at(i)+a+b+c);
			}
		}
	}

	cout<<dp.at(0).at(modpow((long long)2,n,inf)-1)<<endl;

	return 0;
}

template<typename T>
long long modpow(const T n,const T p,const T mod){
	if(p==0) return 1;
	if(p%2==0){
		long long a=modpow(n,p/2,mod);
		return a*a%mod;
	}
	if(p%2==1) return (modpow(n,p-1,mod)*n)%mod;
	cerr<<"ERROR"<<endl;
	return 1;
}

template<typename T>
long long modinv(const T n,const T mod){
	return modpow(n,mod-2,mod);
}

template<typename T>
bool chmax(T &a,const T &b){
	if(a<b){
		a=b;
		return 1;
	}
	return 0;
}

template<typename T>
bool chmin(T &a,const T &b){
	if(a>b){
		a=b;
		return 1;
	}
	return 0;
}

#include <bits/stdc++.h>
#define LL_INFI 0x3f3f3f3f
using namespace std;

long long ** creat2dArray(int N);
void delete2dArray(long long ** dp, int N);

int main ()
{
    int N;
    scanf("%d", &N);

    int X[N + 1];
    int Y[N + 1];
    int Z[N + 1];
    for(int i = 1; i <= N; i++)
        scanf("%d %d %d", &X[i], &Y[i], &Z[i]);

    long long dis[18][18] = {LL_INFI};
    for(int i = 1; i <= N; i++)
    {
        dis[i][i] = 0;
        for(int j = 1; j <= N; j++)
        {
            dis[i][j] = abs(X[j] - X[i]) + abs(Y[j] - Y[i]) + max(0, Z[j] - Z[i]);
        }
    }

    // floyd
    for(int k = 1; k <= N; k++)
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    
    long long **dp = creat2dArray(N);
    for(int i = 1; i < (1 << N); i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(!((i>>j) & 1))
            {
                for(int k = 0; k < N; k++)
                    if((i>>k) & 1)
                        dp[i | (1<<j)][j] = min(dp[i | (1<<j)][j], dp[i][k] + dis[k+1][j+1]);
            }
        }
    }

    long long ans = 1e18;
    for(int i = 0; i < N; i++)
        ans = min(ans, dp[(1<<N) - 1][i] + dis[i+1][1]);
    
    printf("%lld\n", ans);

    delete2dArray(dp, N);

    return 0;
}


long long ** creat2dArray(int N)
{
    // ask for memory
    long long **dp;
    int size = 1 << N;
    dp = new  long long*[size];
    for(int i = 0; i < size; i++)
    {
        dp[i] = new long long[N];
    }
    
    // initialize
    for(int i = 0; i < size; i++)
        for(int j = 0; j < N; j ++)
            dp[i][j] = LL_INFI;

    dp[1][0] = 0;
    
    return dp;
}



void delete2dArray(long long ** dp, int N)
{
    for(int i = 0; i <= (1 << N); i++)
    {
        delete(dp[i]);
    }

    delete(dp);

    return;
}