#include<bits/stdc++.h>

using namespace std;

// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pt;
typedef pair<ll,ll> pll;

#define vint vector<int>
#define vll vector<long long>
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define F(i,n) for(int i = 0;i<n;i++)
#define Fr(i,l,r) for(int i = l;i <= r;i++)
#define rF(i,n) for(int i = n-1;i>=0;i--)
#define Max 1000001
#define intinf 2147483647
#define longlonginf 9223372036854775807
#define MOD 998244353
#define MOD2 1000000007
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define all(arr) arr.begin(),arr.end()
//#define sort(vec) sort(vec.begin(),vec.end())
//#define reverse(vec) reverse(vec.begin(),vec.end())

ll Lpow(ll a,ll b)
{
    ll ans = 1;
    while(b > 0)
    {
        if(b%2)
            ans = (ans*a);
        a = (a*a);
        b = b/2;
    }
    return ans;
}

ll Lpow(ll a,ll b,ll M)
{
	ll ans = 1;
	while(b > 0)
	{
		if(b%2)
			ans = (ans*a)%M;
		a = (a*a)%M;
		b = b/2;
	}
	return ans;
}

struct P {
    int64_t x;
    int64_t y;
    int64_t z;
};
 
int64_t dist(const P& lhs, const P& rhs)
{
    return abs(lhs.x - rhs.x) + abs(lhs.y - rhs.y) + max((int64_t)0, rhs.z - lhs.z);
}
 
int64_t state[1 << 16][16];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(20);
 
 
    int n; cin >> n;
    vector<P> ps(n);
    for (auto& p : ps) {
        cin >> p.x >> p.y >> p.z;
    }
    n--;
 
 
    Fr(i, 1, (1 << n)-1) 
	{
        Fr(j, 0, n-1) 
		{
            if (i & (1 << j)) 
			{
                int pre = i - (1 << j);
                if (pre == 0) 
				{
                    state[i][j] = dist(ps[0], ps[j + 1]);
                }
                else 
				{
                    int64_t cv = INT64_MAX / 1024;
                    Fr(k, 0, n-1) 
					{
                        if (pre & (1 << k)) 
						{
                            cv = min(cv, state[pre][k] + dist(ps[k + 1], ps[j + 1]));
                        }
                    }
                    state[i][j] = cv;
                }
            }
        }
    }
 
    int64_t ans = INT64_MAX;
    Fr(i, 0, n-1) 
	{
        int64_t c = state[(1 << n) - 1][i] + dist(ps[i + 1], ps[0]);
        ans = min(ans, c);
    }
    cout << ans << endl;
 
    return 0;
}
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define INF INT_MAX
#define LLINF LLONG_MAX
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007
#define MODB  998244353 

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
    for (T& x: vec) { is >> x; }
    return is;
}

ll dp[18][1 << 18] = {};

int main() {
	ll ans = 0;
	ll tmp = 0;
	int n; cin >> n;
	ll x[n+1], y[n+1], z[n+1];
	REP(i, n) cin >> x[i] >> y[i] >> z[i];
	x[n] = x[0]; y[n] = y[0]; z[n] = z[0];
	int full = 0; REP(i, n) full += 1 << i;
	REP(bit, 1 << (n+1)){ 
		REP(j, n+1){
			dp[j][bit] = INF;
		}
	}
	dp[0][0] = 0;
	REP1(i, n-1){
		dp[i][1 << (i-1)] = 
			dp[0][0] + abs(x[0] - x[i]) + abs(y[0] - y[i]) + max((ll)0, z[i] - z[0])
		;
		//cout << dp[0][0] + abs(x[0] - x[i]) + abs(y[0] - y[i]) + max((ll)0, z[i] - z[0]) << endl;
	}
	//cout << dp[1][1] << endl;
	REP(bit, 1 << (n+1)){
		REP(j, n+1){
			if(!(bit & (1<<(j-1))) ) continue;
			ll cost = dp[j][bit], here = j;
			//cout << cost << " " << here << " " << bitset<18>(bit) << endl; 
			REP1(i, n){
				dp[i][bit | (1 << (i-1) )] = min( dp[i][bit | (1 << (i-1))], 
					cost + abs(x[here] - x[i]) + abs(y[here] - y[i]) + max((ll)0, z[i] - z[here])
				);
			}
		}
	}
	cout << dp[n][full] << endl;
}