#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;

const int INF=1e8;
void chmin(int& x, int y){ x=min(x,y);}

int main(){
  int n;
  cin >> n;
  vi x(n),y(n),z(n);
  rep(i,n) cin >> x[i] >> y[i] >> z[i];
  int n2=1<<n;
  vvi dist(n,vi(n));
  rep(i,n) rep(j,n) dist[i][j]=abs(x[j]-x[i])+abs(y[j]-y[i])+max(0,z[j]-z[i]);
  vvi dp(n2,vi(n,INF));
  rep(i,n){
    if(i==0) continue;
    dp[1<<i][i]=dist[0][i];
  }
  rep(i,n2){
    rep(j,n){
      if(!(i>>j&1)) continue;
      rep(k,n){
        if(i>>k&1) continue;
        chmin(dp[i|1<<k][k],dp[i][j]+dist[j][k]);
      }
    }
  }
  cout << dp[n2-1][0];
  return 0;
}
#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define PI (2*acos(0.0))
#define eps 1e-9
#define pb push_back
#define endl "\n"
#define watch(x) cout << (#x) << " is " << (x) << endl;
#define show(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi] << " "; cout << endl;
#define showpair(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi].first << " " << v[fi].second << endl;
#define ff first
#define ss second
#define fu cout << "lol" << endl;
#define precision(n) cout << fixed << setprecision(n);
#define lb lower_bound
#define up upper_bound
#define vscan for(i = 0;i<n;i++){cin>>in; v.pb(in);}
#define all(a) a.begin(), a.end()
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define mem(a,val) memset(a,val,sizeof(a))
#define loop(i,n) for(i = 0; i < n; i++)
#define TC ull T; cin>>T; while(T--)
#define IN(x) {scanf("%d",&x);}
#define LL(x) {scanf("%lld",&x);}
#define CC(x) {scanf("%c",&x);}
#define pfl(x) printf("%d\n",x)
#define pfll(x) printf("%lld\n",x)
#define newl puts("")
#define space printf(" ")
#define MOD 1000000007
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ar array

int n;
ar<int,3> arr[20];
ll dp[18][ (1<<20) ];

ll dis(int a, int b){
    return llabs(arr[b][0] - arr[a][0]) + llabs(arr[b][1] - arr[a][1]) + max(0, arr[b][2] - arr[a][2]);
}

ll inf = (1LL<<40);

ll f(int node, int mask){
    if(mask == (1<<n)-1){
        return dis(node,0);
    }
    ll &ret = dp[node][mask];
    if(ret != -1) return ret;
    ret = inf;
    for(int i = 1; i < n; i++){
        if((mask & (1<<i)) == 0){
            ret = min(ret, f(i, mask | (1<<i)) + dis(node,i));
        }
    }
    return ret;
}

void solve(){
    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>arr[i][0];
        cin>>arr[i][1];
        cin>>arr[i][2];
    }
    mem(dp,-1);
    cout << f(0, 1) << endl;

}


int main()
{
    speed;
    solve();
    return 0;
}
