#include<bits/stdc++.h>
using namespace std;
#pragma region atcoder
//#include <atcoder/all>
//using namespace atcoder;
//using mint = modint998244353;
//using mint = modint1000000007;
#pragma endregion
#pragma region macros
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vs = vector<string>;
using vl = vector<ll>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n - 1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define dame { puts("No"); return 0;}
#define y_n {puts("Yes");}else{puts("No");}
#pragma endregion
#pragma region debug for var, v, vv
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){cout << endl;int cnt = 0;for(const auto& v : vv){cout << cnt << "th : "; view(v); cnt++;} cout << endl;}
#pragma endregion

const ll mod = 1000000007;
const int inf = 1001001001;
const ll INF = 1001001001001001001;
const int MAX = 2000005;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

template<class T>bool chmax(T &a, const T b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T b) { if (b<a) { a=b; return 1; } return 0; }
ll modpow(ll a, ll p){ll ret = 1; while(p){if(p & 1){ret = ret * a % mod;} a = a * a % mod; p >>= 1;} return ret;}

/*--------------------------------------------------------------------------------------------------------------------------------*/
ll dist[20][20];
ll dp[(1<<20) + 1][21];
int n;
ll rec(int bit, int v)
{
    // すでに探索済みだったらリターン
    if (dp[bit][v] != -1) return dp[bit][v];

    // 初期値
    if (bit == (1<<v)) {
        return dp[bit][v] = 0;
    }

    // 答えを格納する変数
    ll res = INF;

    // bit の v を除いたもの
    int prev_bit = bit & ~(1<<v);

    // v の手前のノードとして u を全探索
    for (int u = 0; u < n; ++u) {
        if (!(prev_bit & (1<<u))) continue; // u が prev_bit になかったらダメ

        // 再帰的に探索
        if (res > rec(prev_bit, u) + dist[u][v]) {
            res = rec(prev_bit, u) + dist[u][v];
        }
    }
    return dp[bit][v] = res; // メモしながらリターン
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	vl x(n), y(n), z(n);
	rep(i,n) cin >> x[i] >> y[i] >> z[i];
	rep(i,n) rep(j,n) dist[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]) + max(0ll, z[j] - z[i]);
	for (int bit = 0; bit < (1<<n); ++bit){
		for (int v = 0; v < n; ++v){
			dp[bit][v] = -1;
			if(__builtin_popcount(bit) == 1 && (bit & (1 << v))){
				dp[bit][v] = dist[0][v];
			}
		}
	}
	ll res = rec((1<<n)-1, 0);
	cout << res << endl;
} 

#include<stdio.h>
#include<algorithm>
#define nmax 18
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
int n;						//城市数 
struct City{
	int x, y, z;
}city[nmax];
int dp[nmax][1<<nmax];		//到城市，状态的最小花费 
int dis[nmax][nmax];		//城市之间的花费 
int ans=INF;
int dist(City a, City b);
void read();
void create_dis();
void dpprocess();

int main()
{
	read();
	create_dis();
	dpprocess();
	printf("%d", ans);
	return 0;
}

void read()
{
	scanf("%d", &n);
	for( int i=1; i<=n; i++ )
		scanf("%d%d%d", &city[i].x, &city[i].y, &city[i].z);
}

int dist(City a, City b)
{
	return abs(a.x-b.x)+abs(a.y-b.y)+max(0, b.z-a.z);
}

void create_dis()
{
	for( int i=1; i<=n; i++ )
		for( int j=1; j<=n; j++ )
			dis[i][j] = dist(city[i], city[j]);
}

void dpprocess()
{
	memset(dp[0], INF, sizeof(dp));					//fill函数用错了，要加【0】 
//	for( int i=1; i<=n; i++ )
//		for( int j=1; j<(1<<n); j++ )
//			dp[i][j] = INF;
		dp[1][1]=0;
	for( int i=1; i<(1<<n); i++ )				//现在的状态 
		for( int j=1; j<=n; j++ )				//到哪个城市 
		{
			if( i&( 1<<(j-1) ) )				//如果这个状态经过了这个城市 
			{
				for( int k=1; k<=n; k++ )
				{
					if( i&( 1<<(k-1) ) && j!=k )	//试试这个状态其他的经过的城市 
						dp[j][i] = min( dp[j][i], dp[k][i^( 1<<(j-1) )]+dis[k][j] );
				}
			}
		}
	for( int i=2; i<=n; i++ ) 
		ans = min( ans, dp[i][(1<<n)-1]+dis[i][1] );
}