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

const int N = 17;
const int mod = 1e9+ 7;

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

int fx(vector<array<int,3>>&v, int mask , int last ){
    
    if(dp[mask][last] != -1){
      return dp[mask][last];
    }

    int n = v.size();
    
    if(mask == ((1<<n) -1)){
      
      int c = 0;
       for(int j =0;j<3;j++){
              
          if(j == 2){
             c += max(0LL,v[last][j] - v[0][j]);
          }else{
             c += abs(v[last][j] - v[0][j]);
          }
              
        }

       return c;
    }
    
    int ans = INT_MAX;

    for(int i = 1; i < n ; i ++){
       if( (mask&(1<<i)) == 0){
            int c = 0;
            for(int j =0;j<3;j++){
              
              if(j == 2){
                 c += max(0LL,v[last][j] - v[i][j]);
              }else{
                 c += abs(v[last][j] - v[i][j]);
              }
                  
            }

            
            int nca = c + fx(v,mask|(1 << i) ,i);          
            ans = min(ans,nca);

       }
    }

    return (dp[mask][last] = ans);
}

signed main(){

  int n;
  cin>>n;
  
  vector<array<int,3>>v;

  for(int i=0;i<n;i++){
    int x,y,z;
    cin>>x>>y>>z;
    v.push_back({x,y,z});
  }
  
  for(int i=0;i<(1<<n);i++){
      for(int j=0;j<n;j++){
          dp[i][j] = -1;
      }
  }

  int ans = fx(v,1,0);
  cout<<ans<<endl;

  return 0;
}



// //
// n = 2;
// 1 2 3 4 5 ... n

// (1+2) / 2 = > 1

// n = 3
// 1 2 3 

// (1+3)/2 => 2
// (2+2)/2 => 2

// n= 4
// ()

// 1 3 3
// 2 3

// 1 2 3
// 1 3
// 2

// 1 2 3 4 
// 1 2 4
// 1 3
// 2



#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
#define int long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dup(x,y) (((x)+(y)-1)/(y))
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;
const long double PI = (acos(-1));


signed main() {
	int N;
	cin >> N;
	vector<int>X(N), Y(N), Z(N);
	rep(i, N)cin >> X[i] >> Y[i] >> Z[i];
	vector<vector<int>>dist(N, vector<int>(N));
	rep(i, N) {
		rep(j, N) {
			dist[i][j] = abs(X[j] - X[i]) + abs(Y[j] - Y[i]) + max(0ll, Z[j] - Z[i]);
		}
	}

	vector<vector<int>>dp(1ll << N, vector<int>(N));
	rep(i, 1ll<<N)rep(j, N)dp[i][j] = INF;
	dp[1][0] = 0;

	rep(i,(1ll << N)) {
		rep(j, N) {
			if (dp[i][j] == INF)continue;
			rep(k, N) {
				if ((i >> k) % 2 == 1)continue;
				int nexti = i | (1ll << k);
				int nextd = dp[i][j] + dist[j][k];
				dp[nexti][k] = min(dp[nexti][k], nextd);
			}
		}
	}

	int all = (1ll << N) - 1;
	int ret = INF;
	rep(i, N) {
		if (dp[all][i] == INF)continue;
		int tmp = dp[all][i] + dist[i][0];
		ret = min(ret, tmp);
	}
	cout << ret;
}