#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define fi first
#define se second
long long mo = 1000000007;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef pair<ll,Pll> PlP;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;
//using namespace atcoder;

int main(){
    ll N;
    cin >> N;
    vector<ll> X(N), Y(N), Z(N);
    rep(i,N){
        cin >> X[i] >> Y[i] >> Z[i];
    }
    vector<vector<ll>> dp((1LL << N), vector<ll>(N, 1e18));
    dp[1][1] = 0;
    dp[0][1] = 0;
    dp[0][0] = 0;
    dp[1][0] = 0;
    rep(bit, (1LL << N)){
        rep(i,N){
            rep(j,N){
                cmin(dp.at(bit | (1LL << j)).at(j), dp.at(bit | (1LL << i)).at(i) + abs(X[j]-X[i]) + abs(Y[j]-Y[i]) + max(0LL, Z[j] - Z[i]));
            }
        }
    }
    cout << dp[(1LL << N) - 1][0] << endl;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
#define d(x) cerr << #x << " = " << x << endl
const int maxn = 25;
const ll inf = 0x3f3f3f3f;
int n;
ll x[maxn], y[maxn], z[maxn];
ll dis[maxn][maxn];
ll f[maxn][1 << 17];

ll llabs(ll x) {
	if (x < 0) return -x;
	return x;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dis[i][j] = llabs(x[i] - x[j]) + llabs(y[i] - y[j]) + max(0LL, z[j] - z[i]);
			//d(i); d(j); d(dis[i][j]); d(llabs(x[i] - x[j])); d(x[i]); d(x[j]);
		}
	}
	//system("pause");
	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]);
				//d(dis[i][j]); d(i); d(j);
			}
		}
	}
	memset(f, inf, sizeof(f)); f[1][0] = 0;
	for (int S = 0; S < (1 << n); S++) {
		for (int u = 1; u <= n; u++) {
			for (int v = 1; v <= n; v++) {
				if (S >> (v - 1) & 1) {
					f[v][S] = min(f[v][S], f[u][S & ~(1 << (v - 1))] + dis[u][v]);
				}
			}
		}
	}
	ll ans = f[1][(1 << n) - 1];
	for (int i = 2; i <= n; i++) ans = min(ans, f[i][(1 << n) - 1] + dis[i][1]);
	printf("%lld\n", ans);
    return 0;
}