#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define vec(s) vector<s>
#define vvec(s) vector<vector<s>>
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli, lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Yes(x) cout << (x ? "Yes" : "No") << endl;
#define YES(x) cout << (x ? "YES" : "NO") << endl;
#define out(s) cout << s << endl;
#define Reverse(x) reverse(all(x));
#define Sort(x) sort(all(x));
#define pb(s) push_back(s);
#define sp " "
#define INF 10000000000
#define LINF 9000000000000000000
#define all(s) s.begin(), s.end()
void vout(vi v)
{
    for (lli i = 0; i < v.size(); i++)
        cout << v.at(i) << endl;
}
vvi dp(1 << 17, vi(17,-1));
lli n;
vvi place(17, vi(3));
lli rec(lli s, lli v)
{
    if (dp[s][v] >= 0)
    {
        return dp[s][v];
    }
    if (s == (1 << n) - 1 && v == 0)
    {
        return dp[s][v] == 0;
    }
    lli tmp = INF;
    rep(i, n)
    {
        if (!(s >> i & 1))
        {
            lli p = (abs(place[v][0] - place[i][0]) + abs(place[v][1] - place[i][1]) + max((lli)0, place[i][2] - place[v][2]));
            //out("P" << p);
            if (p==0)
            {
                p = INF;
            }
            //out("P" << p <<"S" << s << "G" << v);
            tmp = min(tmp, rec(s | 1 << i, i) +p);
            //out(rec(s | 1 << i, i) + p << "S" << s << "G" << v);
        }
    }
    return dp[s][v]=tmp;
}
int main()
{
    cout << std::fixed << std::setprecision(10);

    cin >> n;
    rep(i, n)
    {
        lli a, b, c;
        cin >> a >> b >> c;
        place[i][0] = a;
        place[i][1] = b;
        place[i][2] = c;
    }
    out(rec(0, 0));
}
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
typedef long long int ll;

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

	int n;cin >> n;
	vector<vector<int>> dist(n, vector<int>(n));
	vector<tuple<int, int, int>> pos;
	vector<vector<int>> dp(n, vector<int>(1 << n, 2e9));
	dp[0][0] = 0;
	for(int i = 0;i < n;i++){
		int x, y, z;cin >> x >> y >> z;
		pos.emplace_back(x, y, z);
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			if(i == j)continue;
			dist[i][j] = abs(get<0>(pos[i]) - get<0>(pos[j])) +
									abs(get<1>(pos[i]) - get<1>(pos[j])) +
									max(0, get<2>(pos[j]) - get<2>(pos[i]));
		}
	}
	for(int i = 0;i < (1 << n);i++){
		for(int j = 0;j < n;j++){
			for(int k = 0;k < n;k++){
				if(j != k && dp[j][i] != INT_MAX){
					dp[k][i | (1 << k)] = min(dp[k][i | (1 << k)], dp[j][i] + dist[j][k]);
				}
			}
		}
	}
	cout << dp[0][(1 << n) - 1] << endl;
}
