#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define ff first
#define ar array
#define ss second
#define ll long long int
#define mem(x) memset(x,0,sizeof(x))
#define setbits(x)  __builtin_popcount(x)
#define ull unsigned long long int
#define all(c) (c).begin(),(c).end()
#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define db double
#define endl "\n"
#define  fbo(x) find_by_order(x)
#define  ook(x) order_of_key(x)
 
using namespace __gnu_pbds;
using namespace std;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair<ll,ll > iil;
typedef pair<ll,int> li;
typedef pair<int,int> ii;
typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    os1;
typedef tree<int, null_type, greater<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    os2;
 
inline void fast()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
const ll pi=31;
const ll MOD[2] = {1187278649, 1149736019};//for double hashing
const ll mod=(ll)(1e9)+7;
ll pmod(ll x,ll n){
  ll r=1;
  while(n>0)
  {
    if(n&1LL)
      r=(r*x)%mod;
    x=(x*x)%mod;
    n=n/2;
    n%=mod;
  }
  return r;
}
ll pMod(ll x,ll n,ll mod)
{ ll r=1;
  while(n>0)
  {
    if(n&1LL)
      r=(r*x)%mod;
    x=(x*x)%mod;
    n=n/2;
    n%=mod;
  }
  return r;
 
}
 
//think recursively also;
ll dp[18][(1<<18)];
void solve()
{
  ll n;
  cin>>n;
  ar<ll,3>node[n+1];
  for(int i=0;i<n;i++)
  {
    cin>>node[i][0]>>node[i][1]>>node[i][2];
  }
  ll dis[n+1][n+1];
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
    {
          dis[i][j]=abs(node[i][0]-node[j][0])+abs(node[i][1]-node[j][1])+max(0LL,(node[j][2]-node[i][2]));
    }
  }
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<(1<<n);j++)
    {
       dp[i][j]=(ll)(1e18);
    }
  }
  dp[0][1]=0;
  for(int j=0;j<(1<<n);j++)
  {
     
     for(int i=0;i<(n);i++)
     {
       if(dp[i][j]==(ll)(1e18))
        continue;
      for(int k=0;k<n;k++)
      {
           if((j>>k)&1)
            continue;
          int x=(j|(1<<k));
          dp[k][x]=min(dp[k][x],dp[i][j]+dis[i][k]);
      }
     }
  }
  ll cost=LLONG_MAX;
  for(int i=1;i<n;i++)
  {
    cost=min(cost,dp[i][(1<<n)-1]+dis[i][0]);
  }
  cout<<cost<<endl;


}  
int main()
{
  fast();
   // int t;
   // cin>>t; 
   // for(int casee=1;casee<=t;casee++)
  {//cout<<"Case #"<<casee<<": ";
    solve();
  }
 
 
 
}
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

inline s64 dis(s64 x, s64 y, s64 z, s64 p, s64 q, s64 r)
{
    return abs(x - p) + abs(y - q) + max(s64(0), r - z);
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<vs64> g(n, vs64(n));
    vs32 x(n), y(n), z(n);
    rep (i, n)
    {
        cin >> x[i] >> y[i] >> z[i];
    }

    rep (i, n) for (int j = i + 1; j < n; ++j)
    {
        s64 d1 = dis(x[i], y[i], z[i], x[j], y[j], z[j]);
        s64 d2 = dis(x[j], y[j], z[j], x[i], y[i], z[i]);
        g[i][j] = d1;
        g[j][i] = d2;
    }

    const s64 inf = 1e18;
    vector< vs64 > dp(1 << n, vs64(n, inf));

    dp[(1 << n) - 1][0] = 0;
    for (int s = (1 << n) - 2; s >= 0; --s)
    {
        rep (v, n)
        {
            rep (u, n)
            {
                if (!(s >> u & 1))
                {
                    dp[s][v] = min(dp[s][v], dp[s | (1 << u)][u] + g[u][v]);
                }
            }
        }
    }

    cout << dp[0][0] << "\n";
    return 0;
}

