#include <iostream>
#include <vector>
#include <tuple>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <iomanip>
#include <algorithm>
#define int long long
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

using namespace std;

const int INF = 1e18;
const int MOD = 1e9 + 7;

void fast()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

vector <vector <int>> dp, a;

int get(int i, int j)
{
	return abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]) + max(0ll, a[j][2] - a[i][2]);
}

signed main()
{
	fast();
	int n;
	cin >> n;
	a.resize(n, vector <int>(3));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < 3; ++j)
			cin >> a[i][j];
	}

	dp.resize(1 << n, vector <int>(n, INF));
	for (int i = 1; i < n; ++i)
	{
		dp[1 << i][i] = get(0, i);
	}

	for (int mask = 0; mask < (1 << n); ++mask)
	{
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (i == j)
					continue;
				dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j],
					dp[mask][i] + get(i, j));
			}
		}
	}

	cout << dp[(1 << n) - 1][0] << '\n';
	return 0;
}

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;

int dp[1<<17][17];
int x[20],y[20],z[20];
int dis[18][18];

int n;

signed main(){
	scanf("%lld",&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++){
		dis[i][i]=0;
		for(int j=1;j<=n;j++){
			dis[i][j]=abs(x[j]-x[i])+abs(y[j]-y[i])+max(0LL,z[j]-z[i]);
		}
	}
	
	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]);
			}
		}
	}
	
	memset(dp,0x3f,sizeof(dp));
	
	dp[1][0]=0;
	
	for(int i=1;i<1<<n;i++){
		for(int j=0;j<n;j++){
			if(!(i>>j&1)){
				for(int k=0;k<n;k++){
					if(i>>k&1){
						dp[i|1<<j][j]=min(dp[i|1<<j][j],dp[i][k]+dis[k+1][j+1]);
					}
				}
			}
		}
	}
	
	int ans=0x3f3f3f3f;
	
	for(int i=0;i<n;i++){
		ans=min(ans,dp[(1<<n)-1][i]+dis[i+1][1]);
	}
	
	printf("%lld\n",ans);
	return 0;
}