#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Max = 1 << 17;
int n;
ll dp[20][20][Max + 10];
ll s[20][20];
ll pos[20][3];
ll p2[20];
int pr[Max + 10];
void pre() {
	for (int i = 0; i < Max; ++i) {
		int n = i;
		while (n) {
			pr[i] += n % 2;
			n /= 2;
		}
	}
	p2[1] = 1;
	for (int i = 2; i < 19; ++i) {
		p2[i] = p2[i - 1] * 2;
	}
}
int main() {
	pre();
	cin >> n;
	const int mx = 1 << (n - 1);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> pos[i][j];
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			s[i][j] = abs(pos[i][0] - pos[j][0]);
			s[i][j] += abs(pos[i][1] - pos[j][1]);
			s[i][j] += max(0ll, pos[j][2] - pos[i][2]);
		}
	}
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k <= mx; ++k)
				dp[i][j][k] = 987654321123456789;
	for (int i = 1; i < n; ++i)
		dp[1][i][p2[i]] = s[0][i];
	for (int _ = 2; _ < n; ++_) {
		for (int i = 1; i < n; ++i) {
			for (int j = 1; j < n; ++j) {
				if (i == j)continue;
				for (int k = 0; k < mx; ++k) {
					if (pr[k] != _ - 1)continue;
					const int& t = p2[i];
					if (t & k)continue;
					dp[_][i][t | k] = min(dp[_][i][t | k], dp[_-1][j][k] + s[j][i]);
				}
			}
		}
	}
	ll mi = 987654321123456789;
	for (int i = 1; i < n; ++i)mi = min(mi, dp[n-1][i][mx - 1] + s[i][0]);
	cout << mi << endl;
	return 0;
}
#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;
}
