#include<bits/stdc++.h>
using namespace std;
const int inf = 5e8;
int dp[20][150000];
int adj[20][20];
int n;
int no[20][3];
int dist(int u, int v){ //u -> v
	return abs(no[u][0]-no[v][0])+abs(no[u][1]-no[v][1]) + max(0,no[v][2]-no[u][2]);
}

int tcp(int u, int mask){
	if(mask ==  (1<<n) - 1)return adj[u][0];
	if(dp[u][mask] != inf) return dp[u][mask];

	for(int v=0;v<n;v++){
		if(v==u || ( mask & (1<<v) )   )continue;
		int d1 = adj[u][v] + tcp(v,mask|(1<<v));
		if(d1 < dp[u][mask]){
			dp[u][mask]=d1;
		}
	}
	return dp[u][mask];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	for(int i=0;i<20;i++){
		for(int j=0;j<150000;j++){
			dp[i][j]=inf;
		}
	}
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			cin>>no[i][j];
		}
	}

	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			adj[i][j]=dist(i,j);
		}
	}
	cout<<tcp(0,1)<<'\n';

	

	return 0;
}
//翻标签不犯规！
//数据范围如此别出心裁。。。
#include<cstdio>
#include<cstring>
#define int long long
#define noti(x,i) x&~(1<<i)
int n;
int f[262155][20];
struct node{int x,y,z;}a[20];
int abs(int x){return x>=0?x:-x;}
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
int dist(int x,int y){
    node c=a[x],d=a[y];
    return
    abs(d.y-c.y)+abs(d.x-c.x)+max(0,d.z-c.z);
}
signed main(){
	memset(f,0x3f,sizeof(f));
	scanf("%lld",&n);
	f[0][0]=0;
	for(int i=0;i<n;++i){
        scanf("%lld%lld%lld",
        &a[i].x,&a[i].y,&a[i].z);
    }
    a[n].x=a[0].x;
    a[n].y=a[0].y;
    a[n].z=a[0].z;
	int siz=1<<n+1;
	for(int i=0;i<siz;++i){
		for(int j=0;j<=n;++j){
			if(i&(1<<j)){
				for(int k=0;k<=n;++k){
					if(i&(1<<k)){
						int w=i|1<<j|1<<k;
						f[w][j]=
						min(f[noti(i,j)][k]
                        +dist(k,j),f[w][j]);
					}
				}
			}
		}
	}
	printf("%lld",f[siz-1][n]);
	return 0;
}