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

const int INF = 1000000001;

void chmin(int& x, int y){
  x = min(x,y);
}

int main() {

  int N;
  cin >> N;

  vector<int> X(N);
  vector<int> Y(N);
  vector<int> Z(N);

  for (int i = 0; i < N; ++i) {
    cin >> X[i] >> Y[i] >> Z[i];
  }

  int N2 = 1<<N;

  vector<vector<int>> dp(N2, vector<int>(N, INF));
  vector<vector<int>> dist(N, vector<int>(N));

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      int current = abs(X[i]-X[j]);
      current += abs(Y[i]-Y[j]);
      current += max(0, Z[j]-Z[i]);
      dist[i][j] = current;
    }
  }

  for (int i = 0; i < N; ++i) {
    if (i == 0) {
      continue;
    }
    dp[1<<i][i] = dist[0][i];
  }

  for (int i = 0; i < N2; ++i) {
    for (int j = 0; j < N; ++j) {
      if (~i>>j&1) {
        continue;
      }
      for (int k = 0; k < N; ++k) {
        if (i>>k&1) {
          continue;
        }
        chmin(dp[i|1<<k][k], dp[i][j] + dist[j][k]);
      }
    }
  }
  
  cout << dp[N2 - 1][0] << endl;
  return 0;

}
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
/*--Input//////////////////////////////////////////////////*/
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
    cin >> first;
    IN(rest...);
    return;
}
#define SS(T, ...)      T __VA_ARGS__; IN(__VA_ARGS__);
#define SV(type,c,n) vector<type> c(n);for(auto& i:c)cin >> i;
/*--Output/////////////////////////////////////////////////*/
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define First(n) cout << ((n) ? "First" : "Second"  ) << endl
inline int p(void){cout << endl; return 0;}
template<class Head> int p(Head&& head){cout << head;p();return 0;} template<class Head,class... Tail> int p(Head&& head,Tail&&... tail){cout<<head<<" ";p(forward<Tail>(tail)...);return 0;}
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

#define vl vector<ll>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) {
  if(a < b) return GCD(b, a);
  if(b==0){
      return a;
  }else{
      return GCD(b,a%b);
  }
}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.second < b.second; }
ll MOD=1e9+7;

const int MAXN=17;
int n;
int d[MAXN][MAXN];
int dp[1<<MAXN][MAXN];

int rec(int S, int v) {
    if(dp[S][v] >= 0) return dp[S][v];
    if(S==(1<<n)-1 && v==0) return dp[S][v]=0;
    int tmp=MOD;
    rep(u,n) if(!(S>>u & 1)) tmp=min(tmp, rec(S|1<<u,u)+d[v][u]);
    return dp[S][v]=tmp;
}

int main() {
    cin>>n;
    vl x(n);
    vl y(n);
    vl z(n);
    rep(i,n)cin>>x[i]>>y[i]>>z[i];
    rep(i,n) rep(j,n) d[i][j]=d[j][i]=MOD;
    rep(i,n){
        rep(j,n){
            if(i!=j)d[i][j]=abs(x[j]-x[i])+abs(y[j]-y[i])+max(0LL,z[j]-z[i]);
        }
    }
    fill((int *)dp, (int *)(dp+(1<<MAXN)), -1);
    cout << rec(0,0) << endl;
}