#include<bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll mod = 1e9 + 7;
const ll linf = 1LL << 62;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

ll dp[20][1 << 20];
int N;
ll X[20], Y[20], Z[20];
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < (1 << N); j++) {
            dp[i][j] = linf;
        }
    }
    dp[0][1] = 0;
    for (int i = 0; i < N; i++) cin >> X[i] >> Y[i] >> Z[i];
    
    for (int i = 0; i < (1 << N); i++) {
        for (int j = 0; j < N; j++) {
            if (dp[j][i] == linf) continue;
            for (int k = 0; k < N; k++) {
                ll cost = abs(X[j] - X[k]) + abs(Y[j] - Y[k]) + max(0LL, Z[k] - Z[j]);
                chmin(dp[k][i | (1 << k)], dp[j][i] + cost);
            }
        }
    }
    ll ans = linf;
    for (int i = 1; i < N; i++) {
        ll cost = abs(X[0] - X[i]) + abs(Y[0] - Y[i]) + max(0LL, Z[0] - Z[i]);
        chmin(ans, dp[i][(1 << N) - 1] + cost);
    }
    cout << ans << endl;
}
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cassert>
#include <numeric>
using namespace std;

#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rept(i,k,n) for(long long i = (k); i < (long long)(n); i++)
#define All(v) v.begin(), v.end()
#define Sort(v) sort(v.begin(),v.end())
#define Rsort(v) sort(v.begin(),v.end(),[](auto a, auto b) { return a > b; })
#define Reverse(v) reverse(v.begin(),v.end())
#define MAX 1000000007
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<long long,long long> Pll;
typedef tuple<int,int,int> Tii;

template <typename T>
ostream& operator<<(ostream& s, const vector<T> &vec){
    for(int i=0;i<vec.size();i++){
        if(i) s << ',';
        else s << '{';
        s <<setw(2)<< vec[i];
    }
    s << '}' << endl;
    return s;
}

int main(){
    bitset<17> b(0);
    int n;
    cin>>n;
    vector<Tii> vs(n);
    rep(i,n){
        int x,y,z;
        cin>>x>>y>>z;
        vs[i]=Tii(x,y,z);
    }
    vector<vector<int> > dp(1<<n,vector<int>(n,1e9));
    dp[0][0]=0;
    sort(vs.begin(), vs.end(), [](Tii a, Tii b) { return get<2>(a) < get<2>(b); });
    for(int i=1;i<(1<<n);i++){ 
        b = i;
        rep(j,n){
            if(b.test(j)){
                rep(k,n){
                    int a,b,c,p,q,r;
                    tie(a,b,c)=vs[k];
                    tie(p,q,r)=vs[j];
                    int dist = abs(p-a)+abs(q-b)+max(0,r-c);
                    dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+dist);
                }
            }
        }

    }
    cout<<dp.back()[0]<<endl;;
    return 0;
}