#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef pair<int,int>  pint;
typedef pair<ll,ll>    pll;
typedef vector<int>    vint;
typedef vector<ll>     vll;
typedef vector<string> vstr;
typedef vector<pint>   vpint;
typedef vector<pll>    vpll;

#define vint2(v,n,m,init) vector<vector<int>> v(n, vector<int>(m, init))
#define vll2(v,n,m,init)  vector<vector<ll>>  v(n, vector<ll>(m, init))

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vint var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vll var(n); rep(i,n){cin >> var[i];}
#define arrst(var, n)    vstr var(n); rep(i,n){cin >> var[i];}
#define ALL(var)         (var).begin(), (var).end()
#define sortall(var)     sort(ALL(var))
#define uniqueall(v)     v.erase(unique(v.begin(), v.end()), v.end());

#define prt(var)         cout << (var) << "\n"
#define prt2(v1, v2)     cout << (v1) << " " << (v2) << "\n"
#define prt3(v1, v2, v3) cout << (v1) << " " << (v2) << " " << (v3) << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << (var) << "\n"
#define prtfill(n, var)  cout << setw(n) << setfill('0') << (var);
#define prtall(v)        rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1?" ":"\n");}
template <typename T>
bool chmax(T &a, const T& b){if(a<b){a=b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a>b){a=b; return true;} return false;}
ll gcd(ll a, ll b){ return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){ return a/gcd(a,b)*b;}
//----------------------------------------------------------------------------

int main(void) {
    ll n;
    cin >> n;
    vector<double> h(n+1);
    h[1] = 1.0;
    REP(i,1,n){
        h[i+1] = h[i] + 1.0/double(i+1);
    }

    prtd(10,double(n)*(h[n])-1.0);
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const int INF = 1<<24;
const ll INFL = (1ll << 60);
//cout << setprecision(20) << 

int n;
int coord[17][3];
int dp[1 << 17][17];

int rec(int S, int v) {
    if (dp[S][v] >= 0) {
        return dp[S][v];
    }

    if (S == (1 << n) - 1 && v == 0) {
        return dp[S][v] = 0;
    }

    int res = INF;
    for (int u = 0; u < n; u++) {
        if (!(S >> u & 1)) {
            int a, b, c, p, q, r;
            a = coord[v][0];
            b = coord[v][1];
            c = coord[v][2];
            p = coord[u][0];
            q = coord[u][1];
            r = coord[u][2];
            int dist = abs(a - p) + abs(b - q) + max(r - c, (int)0);
            res = min(res, rec(S | 1 << u, u) + dist);
        }
    }
    return dp[S][v] = res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        ll x, y, z; cin >> x >> y >> z;
        coord[i][0] = x;
        coord[i][1] = y;
        coord[i][2] = z;
    }
    memset(dp, -1, sizeof(dp));
    cout << rec(0, 0) << endl;
}