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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, res = INT_MAX;
    cin >> n;
    vector<vector<int>> p(n, vector<int>(3));
    for (auto& i : p) {
        for (auto& j : i) {
            cin >> j;
        }
    }
    auto calc = [&](int x, int y) {
        return abs(p[x][0] - p[y][0]) + abs(p[x][1] - p[y][1]) + max(0, p[y][2] - p[x][2]);
    };
    vector<vector<int>> dp(1 << n, vector<int>(n, 1e9));
    dp[1][0] = 0;
    for (int s = 0; s < (1 << n); s++) {
        for (int j = 0; j < n; j++) { // 枚举 当前经过的最后那个点
            if (!(s & (1 << j))) continue;
            for (int k = 0; k < n; k++) { // 枚举 将要前往的点
                if (s & (1 << k)) continue;
                dp[s | (1 << k)][k] = min(dp[s | (1 << k)][k], dp[s][j] + calc(j, k));
            }
        }
    }
    for (int i = 0; i < n; i++) {
        res = min(res, dp[(1 << n) - 1][i] + calc(i, 0));
    }
    cout << res;
    return 0;
}

#include<iostream>
#include<string>
#include<vector>
#include<deque>
#include<algorithm>
#include<stack>
#include<iomanip>  
#include<queue>
#include<map>
#include<math.h>
#include<climits>
#include<limits.h>

using namespace std;

const int N = 17, M = 272144;
int x[N], y[N], z[N];
int dp[M][N];

int dis(int f, int s) {
    return abs(x[f] - x[s]) + abs(y[f] - y[s]) + max(0, z[s] - z[f]);
}

int solve(int lst, vector <bool> v, bool is_back = false) {
    if (is_back) {
        if (lst == 0)
            return 0;
    }
    int h = 0;
    for (int i = 0; i < (int)v.size(); i++) {
        h *= 2;
        h += (int)v[i];
    }
    h *= 2;
    h += (int)is_back;
    if (dp[h][lst] != -1)
        return dp[h][lst];
    bool f = true;
    for (int i = 0; i < (int)v.size(); i++)
        if (!v[i])
            f = false;
    if (lst == 0 && f) {
        return 0;
    }
    if (f) {
        for (int i = 0; i < (int)v.size(); i++) {
            v[i] = false;
        }
        v[lst] = true;
        return solve(lst, v, true);
    }
    int ans = INT_MAX;
    for (int i = 0; i < (int)v.size(); i++) {
        if (v[i])
            continue;
        v[i] = true;
        int t = solve(i, v, is_back) + dis(lst, i);
        ans = min(ans, t);
        v[i] = false;
    }
    return dp[h][lst] = ans;
}

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> z[i];
    }
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            dp[i][j] = -1;
    vector <bool> v;
    for (int i = 0; i < n; i++)
        v.push_back(false);
    v[0] = true;
    cout << solve(0, v)<<'\n';
}
