#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct nodes{
	ll x,y,z;
}node;
node m[3000];
ll d[300][300];
ll dp[1<<18][18];
int main()
{
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>m[i].x>>m[i].y>>m[i].z;
	 }
	 for(ll i=1;i<=n;i++)
	 {for(ll j=1;j<=n;j++)
	 {
	 	d[i][j]=abs(m[i].x-m[j].x)+abs(m[i].y-m[j].y)+max((ll)0,m[j].z-m[i].z);
	 }
	 }
	for(ll k=1;k<=n;k++)
	{
		for(ll i=1;i<=n;i++)
		{
			for(ll j=1;j<=n;j++)
			{
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	ll x=1<<n;
	for(int i=0;i<1<<18;i++)
	for(int j=0;j<18;j++)
	dp[i][j]=(ll)99999999999999;



	dp[1][0]=(ll)0;
	for(ll i=1;i<1<<n;i++)
	{
		for(ll j=0;j<n;j++)
		{
			if((i>>j&1)==0)
			{
				for(ll k=0;k<n;k++)
				if(i>>k&1)
				dp[i|1<<j][j]=min(dp[i][k]+d[k+1][j+1],dp[i|1<<j][j]);
			}
		}
	}

		ll ans=999999999999;
for(int i=0;i<n;i++){
    ans=min(ans,dp[(1<<n)-1][i]+d[i+1][1]);
  }
		cout<<ans;

	return 0;
 }

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;

ll n;
vector<ll> x, y, z;
ll dp[1ll<<18][20];
const ll INF = 1ll<<60;
ll rec(ll s, ll v){
    if(dp[s][v] != 0) return dp[s][v];
    if(s == (1<<n) - 1 && v==0) return 0;

    ll ret = INF;
    for(ll nv = 0; nv < n; ++nv){
        if(s & (1<<nv)) continue;

        ret = min(ret, rec((s|(1<<nv)), nv) + abs(x[v]-x[nv]) + abs(y[v]-y[nv]) + max(0ll, z[nv]-z[v]));
    }

    return dp[s][v] = ret;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n;
    x.resize(n);
    y.resize(n);
    z.resize(n);
    rep(i, n) cin >> x[i] >> y[i] >> z[i];

    cout << rec(0, 0) << endl;


    return 0;
}