/*** author: yuji9511 ***/
#include <bits/stdc++.h>
// #include <atcoder/all>
// using namespace atcoder;
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << "\n"
ll dp[18][1LL<<18] = {};
ll dist[20][20] = {};


void solve(){
    ll N;
    cin >> N;
    ll X[20], Y[20], Z[20];
    rep(i,0,N) cin >> X[i] >> Y[i] >> Z[i];
    rep(i,0,N){
        rep(j,0,(1LL<<N)){
            dp[i][j] = INF;
        }
    }
    rep(i,0,N){
        rep(j,0,N){
            if(i == j){
                dist[i][j] = 0;
            }else{
                dist[i][j] = abs(X[i]-X[j]) + abs(Y[i]-Y[j]) + max(0LL, Z[j]-Z[i]);
            }
        }
    }
    
    dp[0][1] = 0; //dp[i][j]: 今iにいて訪れたことのある頂点集合がjの時の最短距離
    rep(bit,0,(1LL<<N)){
        rep(i,0,N){
            if(dp[i][bit] == INF) continue;
            rep(j,0,N){
                if((bit>>j) & 1) continue;
                dp[j][bit | (1LL<<j)] = min(dp[j][bit | (1LL<<j)], dp[i][bit] + dist[i][j]);
            }
        }
    }
    ll ans = INF;
    rep(i,0,N){
        ans = min(ans, dp[i][(1LL<<N)-1] + dist[i][0]);
    }
    if(ans == INF){
        print(-1);
    }else{
        print(ans);
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <climits>

using namespace std;
using ll = int64_t;

struct Point{
	int x;
	int y;
	int z;
};

inline int D(const Point& l, const Point& r)
{
	return abs(r.x - l.x) + abs(r.y - l.y) + max(0, r.z - l.z);
}

int tsp(const vector<vector<int>>& cities, int pos, int visited, vector<vector<int>>& state)
{
	if(visited == ((1 << cities.size()) - 1))
		return cities[pos][0]; // return to starting city

	if(state[pos][visited] != INT_MAX)
		return state[pos][visited];

	for(int i = 0; i < cities.size(); ++i)
	{
		// can't visit ourselves unless we're ending & skip if already visited
		if(i == pos || (visited & (1 << i)))
			continue;

		int distance = cities[pos][i] + tsp(cities, i, visited | (1 << i), state);
		if(distance < state[pos][visited])
			state[pos][visited] = distance;
	}

	return state[pos][visited];
}

int main()
{
	int n;
	cin >> n;
	vector<Point> points(n);
	for (int i = 0; i < n; ++i) {
		cin >> points[i].x >> points[i].y >> points[i].z;
	}

	vector<vector<int>> d(n);
	for (int i = 0; i < n; ++i) {
		d[i].resize(n);
		for (int j = 0; j < n; ++j) {
			d[i][j] = D(points[i], points[j]);
		}
	}

	vector<vector<int>> state(n);
	for (auto& y : state) {
		y = vector<int>((1 << n) - 1, INT_MAX);
	}
	cout << tsp(d, 0, 1, state) << "\n";

	return 0;
	int minPath = INT_MAX;
	vector<int> v(n - 1);
	for (int i = 0; i < v.size(); ++i) {
		v[i] = i + 1;
	}

	do {
		int current = 0;
		int k = 0;

		for (int i = 0; i < v.size(); ++i) {
			current += d[k][v[i]];
			k = v[i];
		}
		current += d[k][0];
		minPath = min(minPath, current);
	} while (next_permutation(v.begin(), v.end()));

	cout << minPath << "\n";

	return 0;
}
