#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans = 0;
template<typename T>
struct HamiltonGraph {
    int n;
    T M;
    vector<vector<T>> DP, dt, rt;
    const T INF = numeric_limits<T>::max();

    HamiltonGraph (const int n_) : n(n_), M(1ll<<n_) {
        dt.assign(n_, vector<T>(n_, INF));
    }

    T Calc_MinimumCost (int s, int g = -1){
        DP.assign(M, vector<T>(n, INF));
        rt.assign(M, vector<T>(n, -1));
        DP[1<<s][s] = 0;
        for(ll i = 0; i < M; i++){
            for(int j = 0; j < n; j++){
                if(i & (1ll<<j)){
                    for(int k = 0; k < n; k++){
                        if(DP[i][j] != INF && DP[i|(1ll<<k)][k] > DP[i][j]+dt[j][k]){
                            DP[i|(1ll<<k)][k] = DP[i][j]+dt[j][k];
                            rt[i|(1ll<<k)][k] = j;
                        }
                    }
                }
            }
        }
        if(g < 0) g = min_element(DP[M-1].begin(), DP[M-1].end())-DP[M-1].begin();
        return DP[M-1][g];
    }

    vector<int> Build_ShortestPath (int s = 0, int g = -1){
        vector<int> path;
        T m = M-1;
        if(g < 0) g = min_element(DP[M-1].begin(), DP[M-1].end())-DP[M-1].begin();
        int now, nxt; now = nxt = g;
        if(s == g){
            path.push_back(g);
            now = nxt = rt[m][g];
            ans += dt[now][g];
        }
        while(m != (1<<s) || now != s){
            path.push_back(now);
            now = rt[m][now];
            ans += dt[now][nxt];
            m ^= (1<<nxt);
            nxt = now;
        }
        path.push_back(now);
        reverse(path.begin(), path.end());
        return path;
    }
};

int main() 
{
 
    int n;
    cin >> n; 
 
    vector<ll> x(n),y(n),z(n);
 
    for (ll i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> z[i];
    }
 
    HamiltonGraph<ll> g(n);
    for (ll i = 0; i < n; i++){ 
        for (ll j = 0; j < n; j++){ 
            if(z[j]-z[i] > 0) g.dt[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]) + z[j]-z[i]; 
            else g.dt[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]);
        }
    }
    g.Calc_MinimumCost(0,0);
    g.Build_ShortestPath(0,0);
    cout << ans << endl;
    return 0; 
}


#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cerr<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

const int MAX_N = 18;

int dp[(1<<MAX_N)][MAX_N];

void init(){
  rep(i,(1<<MAX_N)){
    rep(j,MAX_N){
      dp[i][j] = INF;
    }
  }
}

int main() {
  int n; cin >> n;
  vector<vector<int> > dist(n,vector<int>(n,-INF));
  vi x(n), y(n), z(n);
  rep(i,n){
    cin >> x[i] >> y[i] >> z[i];
  }


  rep(i,n){
    rep(j,n){
      if(i == j){
        dist[i][j] = 0;
        continue;
      }
      dist[i][j] = abs(x[j]-x[i]) + abs(y[j]-y[i]) + max(0,z[j]-z[i]);
    }
  }



  init();
  rep(i,n){
    if(i == 0) continue;
    dp[1<<i][i] = dist[0][i];
  }


  rep(b,(1<<n)){
    if(b == 0) continue;
    rep(j,n){
      if(!((b>>j)&1)) continue;
      rep(k,n){
        if((b>>k)&1) continue;
        dp[b|(1<<k)][k] = min(dp[b|(1<<k)][k], dp[b][j]+dist[j][k]);
      }
    }
  }
  cout << dp[(1<<n)-1][0] << endl;
  

  return 0; 
}
