#include<stdio.h>
#include<math.h>
#include<algorithm> 
#define it register int
#define ct const int
#define il inline
typedef long long ll;
#define rll register ll
#define cll const ll
#define mkp make_pair 
using namespace std;
const int N=30;
const ll inf=1e15;
int n,x[N],y[N],z[N],pw[N];
ll w[N][N],f[20][1<<19];
il int A(ct x){return x<0?-x:x;}
il int Max(ct p,ct q){return p>q?p:q;}
il ll Min(cll p,cll q){return p<q?p:q;}
int main(){
	scanf("%d",&n);it i,j,s;
	for(i=pw[0]=1;i<=30;++i) pw[i]=pw[i-1]<<1;
	for(i=0;i<n;++i) scanf("%d%d%d",&x[i],&y[i],&z[i]);
//	x[n]=x[1],y[n]=y[1],z[n]=z[1],++n;
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			w[j][i]=A(x[i]-x[j])+A(y[i]-y[j])+Max(z[i]-z[j],0); 
	//printf("%d %d\n",w[0][1]);
	ct lim=1<<n;
	for(i=0;i<n;++i) for(j=0;j<=lim;++j) f[i][j]=inf;
	f[0][1]=0;
	for(s=0;s<lim;++s)
		for(i=0;i<n;++i)
			if(f[i][s]<inf){
				for(j=0;j<n;++j){
					if(s>>j&1) continue;
		//			if(i==0&&j==n-1) continue;
					f[j][s|pw[j]]=Min(f[j][s|pw[j]],f[i][s]+w[i][j]);
				}
			}
	rll ans=inf;
	for(i=1;i<n;++i) ans=Min(ans,f[i][lim-1]+w[i][0]);
	printf("%lld",ans);
//	printf("%lld",f[n-1][lim-1]); 
	return 0;
}
/*
f[i][S]=现在走到 i，已经走了的状态集合是S 
f[j][S|pw[j]]=f[i][S]+a[i][j]
*/

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(), a.end()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 20;
const ll inf = 1e18 + 5;

int n;
array<ll,3> niz[maxn];

ll dp[maxn][(1 << 17)];

ll dist[maxn][maxn];

ll memo(int x, int mask){
    if(mask == (1 << n) - 1)return dist[x][0];
    if(dp[x][mask] != -1)return dp[x][mask];
    ll ans = inf;
    ff(i,0,n - 1){
        if(!(mask & (1 << i)))ans = min(ans, dist[x][i] + memo(i, mask | (1 << i)));
    }
    return dp[x][mask] = ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> n;
    ff(i,0,n - 1){
        ff(j,0,2)cin >> niz[i][j];
    }
    ff(i,0,n - 1){
        ff(j,0,n - 1)dist[i][j] = abs(niz[i][0] - niz[j][0]) + abs(niz[i][1] - niz[j][1]) + max(0ll, niz[j][2] - niz[i][2]);
    }
    memset(dp, -1, sizeof(dp));
    cout << memo(0, 1) << endl;
    return 0;
}
/**



// probati bojenje sahovski ili slicno

**/
