#include <bits/stdc++.h>
 
#define rep(i,n) for (int i = 0; i < (n); ++i)
 
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vvi = vector<vector<int>>;
using vi = vector<int>;
 
const ll MOD = 1e9 + 7;
const int INF = 1001001001;
const double PI = 3.14159265358979323846;

int V;
int G[20][20];
int dp[200000][20];

struct pos {
    int x, y, z;
    pos(int x, int y, int z) : x{x}, y{y}, z{z} {}
};

int rec(int state, int v) {
    if (state == 0) {
        if (v == 0) {
            return 0;
        } else {
            return INF;
        }
    }
    if ((state & (1 << v)) == 0) {
        return INF;
    }

    int &ret = dp[state][v];
    if (ret != 0) return ret;

    ret = INF;
    rep(u, V) {
        ret = min(ret, rec(state ^ (1 << v), u) + G[u][v]);
    }
    return ret;
}


void solve() {
    cin >> V;
    
    rep(i, 20) rep(j, 20) G[i][j] = INF;

    vector<pos> vec;
    int x, y, z;
    vector<int> zs;
    rep(i, V) {
        cin >> x >> y >> z;
        x--; y--; z--;
        vec.push_back(pos(x, y, z));
        zs.push_back(z);
    }
    
    rep(i, V) {
        auto a = vec[i];
        rep(j, V) {
            auto b = vec[j];
            int dist = abs(a.x - b.x) + abs(a.y - b.y);
            G[i][j] = dist + max(0, b.z - a.z);
            G[j][i] = dist + max(0, a.z - b.z);
        }
    }

    int state = (1 << V) - 1;
    int ans = rec(state, 0);

    if (ans == INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
}

int main() {
    solve();
    return 0;
}
//#define LOCAL
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 500;
const int inf  = 1 << 29;

const int N = 17;
int n;
int dp[N][1<<N];
int dis[N][N];
int pos[N][3];

int dfs(int city, int state) {
	if(state == (1 << n) - 1) {
		return dis[city][0];
	}
	if(dp[city][state] != -1) return dp[city][state];
	dp[city][state] = inf;
	for(int i = 0; i < n; i++) {
		if(state & (1 << i)) continue;
		dp[city][state] = min(dp[city][state], dis[city][i] + dfs(i, state | (1 << i)));
	}
	return dp[city][state];
}

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
	freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d%d%d", &pos[i][0], &pos[i][1], &pos[i][2]);
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			dis[i][j] = abs(pos[i][0] - pos[j][0]) + abs(pos[i][1] - pos[j][1]) + max(0, pos[j][2] - pos[i][2]);
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			for(int k = 0; k < n; k++) {
				dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
			}
		}
	}
	memset(dp, 255, sizeof(dp));
	dfs(0, 1<<0);
	printf("%d", dp[0][1<<0]);
    return 0;
}