// E - Traveling Salesman among Aerial Cities
// 典型: 巡回セールスマン問題
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);++i)

int main(){
	int n; cin>>n;
	vi x(n), y(n), z(n); rep(i, n) cin>>x[i]>>y[i]>>z[i];
	int m = 1<<n;
	vector<vi> dp(m, vi(n, 1'000'000'000));
	dp[m-1][0] = 0;
	for(int S=m-2; S>=0; --S){
		rep(v, n) rep(u, n){
			if(S>>u & 1) continue;
			int d = max(0, z[u] - z[v]);
			d += abs(x[u]- x[v]) + abs(y[u]- y[v]);
			dp[S][v] = min(dp[S][v], dp[S | 1<<u][u] + d);
		}
	}
	cout<< dp[0][0] <<endl;
}

#include<bits/stdc++.h>

#define SORT(v) sort(v.begin(),v.end())
#define si(n) scanf("%d",&n)
#define sii(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define ss(cad) scanf("%s",cad)
#define all(v) (v).begin(), (v).end()
#define PB push_back
#define fst first
#define scn second
#define DBG(x) cerr << #x << " = " << (x) << endl; 
#define M 1000000007
#define N_MAX 100010

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef vector<pi> vp;

int a[20], b[20], c[20];
int dp[1<<18][17];
int pre[18];

int dist(int x, int y){
	return abs(a[y] - a[x]) + abs(b[y] - b[x]) + max(0, c[y] - c[x]); 
}

int main(){
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	int n;
	si(n);
	for(int i = 0; i < n; i++){
		sii(a[i], b[i]);
		si(c[i]);
		pre[i] = (1<<i);
	}
	pre[n] = (1<<n);

	for(int mask = 1; mask < pre[n]; mask++){
		for(int i = 0; i < n; i++){
			if(mask&pre[i]){
				int tmp = mask^pre[i];
				if(tmp == 0)
					dp[mask][i] = dist(0, i); 
				for(int p = 0; p < n; p++){
					if(tmp&pre[p])
						dp[mask][i] = min(dp[mask][i], dp[tmp][p] + dist(p, i));
				}
			}
		}
	}
	printf("%d\n", dp[(1<<n)-1][0]);
	return 0;
}
