#include<iostream>
#include<algorithm>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, P> State;

int closed[17][1<<17];

int main(){
  int n;
  cin >> n;
  ll t[17][3];
  for (int i = 0; i < n; i++) {
    cin >> t[i][0] >> t[i][1] >> t[i][2];
  }
  memset(closed, -1, sizeof(closed));
  closed[0][0] = 0;
  priority_queue< State, vector<State>, greater<State> > open;
  open.push(State(0, P(0, 0)));
  while (!open.empty()) {
    State st = open.top(); open.pop();
    ll cost = st.first;
    int pos = st.second.first;
    int used = st.second.second;
    if (pos == 0 && used == (1 << n) - 1) {
      cout << cost << endl;
      break;
    }
    if (closed[pos][used] != -1 && closed[pos][used] < cost) {
      continue;
    }
    for (int nextPos = 0; nextPos < n; nextPos++) {
      if (nextPos == pos) {
        continue;
      }
      int nextUsed = used | (1 << nextPos);
      ll nextCost = cost + abs(t[nextPos][0] - t[pos][0]) + abs(t[nextPos][1] - t[pos][1]) + max(0LL, t[nextPos][2] - t[pos][2]);
      if (closed[nextPos][nextUsed] == -1 || closed[nextPos][nextUsed] > nextCost) {
        open.push(State(nextCost, P(nextPos, nextUsed)));
        closed[nextPos][nextUsed] = nextCost;
      }
    }
  }
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
ll mod=1e9 +7;
ll dp[17][(1<<17)],n;

ll cost(pair<pair<ll,ll>,ll> &p1,pair<pair<ll,ll>,ll> &p2)
{
    return max((ll)0,p2.second-p1.second)+abs(p1.first.first-p2.first.first)+abs(p1.first.second-p2.first.second);
}

ll solve(vector<pair<pair<ll,ll>,ll> > v,ll idx,ll mask)
{
    if(mask== (1<<n)-1)
    {
        return cost(v[idx],v[0]);
    }
    if(dp[idx][mask]!=-1) return dp[idx][mask];
    dp[idx][mask]=1e9;
    for(int i=0;i<n;i++)
    {
        if(mask&(1<<i)) {}
        else
        {
            dp[idx][mask]=min(dp[idx][mask],cost(v[idx],v[i])+solve(v,i,mask|(1<<idx)));
        }
    }
    // cout<<idx<<" "<<mask<<" "<<dp[idx][mask]<<endl;
    return dp[idx][mask];
}


int main()
{
    cin>>n;
    vector<pair<pair<ll,ll>,ll> > v(n);
    for(int i=0;i<n;i++)
        cin>>v[i].first.first>>v[i].first.second>>v[i].second;
    memset(dp,-1,sizeof dp);
    cout<<solve(v,0,0);
}