#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <iostream>
#include <sstream>
#include <ostream>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <iomanip>
#include <set>
#include <bitset>
//#include<unordered_map>
#define INT_MINs -2000000000
#define INT_MAXs 1000000001
#define MID int mid=(l+r)/2
#define REP1(i,x,y) for(int i=x;i<y;i++)
#define REP2(i,x,y) for(int i=x;i<=y;i++)
#define ls (2*k)
#define rs (2*k+1)
#define lson l,mid,2*k
#define rson mid+1,r,2*k+1
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(0);cin.tie(NULL);
#define pb(a) push_back(a)
#define pi acos(-1)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=20210213;
const ll ba=131;
//ll qk(ll x,ll y){ll ans=1;while(y){if(y&1) ans=ans*x;y>>=1;x=x*x;}return ans;}
const int dx[8] = { 0,-1,0,1,-1,-1,1,1}, dy[8] = { -1,0,1,0,-1,1,-1,1};
const int dxx[8]= {2,1,-1,-2,-2,-1, 1, 2},dyy[8]= {1,2,2,1, -1,-2,-2,-1};
int a[20],b[20],c[20];
int minn=inf;
int n;
int vis[20];
int dp[1000005][20];

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    memset(dp,inf,sizeof dp);
    dp[1][1]=0;
    for(int i=1;i<(1<<n);i++){
        for(int j=1;j<=n;j++){
            if((1<<(j-1))&i==0) continue;
            for(int k=1;k<=n;k++){
                if((1<<(k-1))&i) continue;
                dp[i|(1<<(k-1))][k]=min(dp[i|(1<<(k-1))][k],dp[i][j]+abs(a[k]-a[j])+abs(b[k]-b[j])+max(0,c[k]-c[j]));
            }
        }
    }
    for(int i=1;i<=n;i++){
        minn=min(dp[(1<<n)-1][i]+abs(a[1]-a[i])+abs(b[1]-b[i])+max(0,c[1]-c[i]),minn);
    }
    cout<<minn<<endl;
}
int main()
{
    IOS;
    solve();
    return 0;
}

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define all(A) A.begin(),A.end()
typedef long long ll;

vector<int> x,y,z;

int dist(int a,int b){
  return abs(x[b]-x[a])+abs(y[b]-y[a])+max(0,z[b]-z[a]);
}

void infout(int a){
  if(a == 1e9) cout << "INF";
  else cout << a;
  cout << ",";
}

void chmin(int& a, int b){
  a = min(a,b);
}

int main(){
  
  int n;
  cin >> n;
  x.resize(n);
  y.resize(n);
  z.resize(n);
  rep(i,n) cin >> x[i] >> y[i] >> z[i];
  vector<vector<int>> dp(1<<n,vector<int>(n,1e9));
  rep(i,n){
    if(i == 0) continue;
    dp[1<<i][i] = dist(0,i);
  }
  rep(i,1<<n){
    //from where?
    rep(from,n){
      //to where?
      rep(to,n){
        chmin(dp[i|1<<to][to],dp[i][from]+dist(from,to));
      }
    }
  }
  cout << dp[(1<<n)-1][0] << endl;
}