#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n - 1; i >= 0; i--)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;

struct City {
    int x, y, z;
    City() {}
    City(int x, int y, int z) {
        this->x = x;
        this->y = y;
        this->z = z;
    }
};

int dist(City c1, City c2) {
    return abs(c2.x - c1.x) + abs(c2.y - c1.y) + max(0, c2.z - c1.z);
}

int main() {
    int n;
    cin >> n;
    vector<City> city(n);
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        city[i] = {x, y, z};
    }
    vector<vector<int>> dp(n, vector<int>(1<<n, INF));
    dp[0][0] = 0;
    for (int i = 0; i < (1<<n); i++) {
        for (int j = 0; j < n; j++) {
            if (not (i & (1<<j))) {
                for (int k = 0; k < n; k++) {
                    dp[j][i | (1<<j)] = min(dp[j][i | (1<<j)], dp[k][i] + dist(city[k], city[j]));
                }
            }
        }
    }
    int ans = dp[0][(1<<n) - 1];
    cout << ans << endl;
}
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define pp pair<ll,ll>
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
int inf=1000001000;
ll INF=2e18;
ll MOD=1000000007;
ll mod=998244353;

int main() {
   int n;
   cin >> n;
   vector<int> x(n),y(n),z(n);
   vector<int> t(n+1);
   rep(i,n) t[i]=pow(2,i);
   rep(i,n) cin >> x[i] >> y[i] >> z[i];
   int e=pow(2,n);
   vector<vector<int>> a(n,vector<int>(e,inf));
   a[0][1]=0;
   rep(i,n-1){
       rep(j,e){
           int u=j;
           rep(k,n){
               if (u%2==0){
                   rep(ii,n){
                       a[k][j+t[k]]=min(a[k][j+t[k]],a[ii][j]+abs(x[ii]-x[k])+abs(y[ii]-y[k])+max(0,z[k]-z[ii]));
                   }
               }
               u/=2;
           }
       }
   }
   int ans=inf;
   rep(i,n) ans=min(ans,a[i][e-1]+abs(x[0]-x[i])+abs(y[0]-y[i])+max(0,z[0]-z[i]));
   cout << ans << endl;
}
