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

const int64_t MOD = 1e9 + 7;
const int64_t MOD2 = 998244353;
const int INF = 1e9;

long long dist(int i, int j, vector<long long> &x, vector<long long> &y, vector<long long> &z) {
  return abs(x.at(j) - x.at(i)) + abs(y.at(j) - y.at(i)) + max(0LL, z.at(j) - z.at(i));
}

int main() {
  int n;
  cin >> n;
  vector<long long> x(n), y(n), z(n);
  for (int i=0; i<n; i++) {
    cin >> x.at(i) >> y.at(i) >> z.at(i);
  }
  vector<vector<long long>> dp(1<<n, vector<long long>(n+1, INF));
  dp.at(1).at(0) = 0;
  for (int bit = 0; bit < (1<<n); bit++) {
    for (int v=0; v<n; v++) {
      if (!(bit & (1<<v))) continue;
      for (int nv=0; nv<n; nv++) {
        if (bit & (1<<nv)) continue;
        int nbit = bit | (1<<nv);
        dp.at(nbit).at(nv) = min(dp.at(nbit).at(nv), dp.at(bit).at(v) + dist(v, nv, x, y, z));
      }
    }
  }
  long long ans = INF;
  for (int i=0; i<n; i++) {
    ans = min(ans, dp.at((1<<n) - 1).at(i) + dist(i, 0, x, y, z));
  }
  cout << ans << endl;
}

#include <bits/stdc++.h>
#define var long long
#define FOR(i, st, en) for (int i = st, _en = (en); i <= _en; ++i)
#define REP(i, en) for (int i = 0, _en = (en); i < _en; ++i)
#define FORD(i, st, en) for (int i = st, _en = (en); i >= _en; --i)
#define MASK(n) (1 << (n))
#define BIT(x, i) (((x)>>(i)) & 1)
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define taskname ""
#define file                              \
	freopen(taskname".INP", "r", stdin); \
	freopen(taskname".OUT", "w", stdout)
using namespace std;
typedef pair<int, int> ii;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
template<class T> bool minimize(T& x, const T& y) {
	if (x > y) {x = y; return true;}
	return false;
}
template<class T> bool maximize(T& x, const T& y) {
	if (x < y) {x = y; return true;}
	return false;
}
// ----------------------------------------------------------------------------------
#define maxn 20
struct Point {int x, y, z;};
int caldist(const Point &a, const Point &b) {
    return abs(a.x-b.x) + abs(a.y-b.y) + max(0, b.z-a.z);
}

int n;
Point a[maxn];
int dist[maxn][maxn];
int x[maxn], cost[maxn];
bool check[maxn];
int dp[maxn][MASK(maxn)];
int res = inf;
// ----------------------------------------------------------------------------------
void sub1() {
    vector<int> vertex(n-1);
    iota(vertex.begin(), vertex.end(), 2);
    do {
        int cur = 0;
        int last = 1;
        REP(i, vertex.size()) {
            cur += dist[last][vertex[i]];
            last = vertex[i];
        }
        cur += dist[last][1];
        minimize(res, cur);
    } while (next_permutation(vertex.begin(), vertex.end()));

    cout << res << endl;
}

void recursion(int i) {
    FOR(j, 2, n) if (!check[j]) {
        x[i] = j; cost[i] = cost[i-1]+dist[x[i-1]][j];
        if (cost[i] < res) {
            if (i < n) {
                check[j] = true;
                recursion(i+1);
                check[j] = false;
            }
            else minimize(res, cost[n]+dist[x[n]][1]);
        }
    }
}
void sub2() {
    check[1] = true;
    x[1] = 1; cost[1] = 0;
    recursion(2);

    cout << res << endl;
}

int cal(int i, int s) {
    if (__builtin_popcount(s) == n) return dist[i][1];
    if (dp[i][s] > -1) return dp[i][s];

    int tmp = inf;
    FOR(j, 2, n) if (BIT(s, j) == 0)
        minimize(tmp, cal(j, s|MASK(j))+dist[i][j]);
    
    return dp[i][s] = tmp;
}
void sub3() {
    memset(dp, -1, sizeof dp);
    cout << cal(1, 2) << endl;
}

void test_case() {
    cin >> n;
    FOR(i, 1, n) cin >> a[i].x >> a[i].y >> a[i].z;
    FOR(i, 1, n) FOR(j, 1, n) if (i != j)
        dist[i][j] = caldist(a[i], a[j]);

    sub3();
}

int main() {
	fastio;
	// file;

	int test = 1;
	// scanf("%d", &test);
	while (test--) test_case();
	return 0;
}
