#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int INF = 1e9;
int dp[1 << 18][18];
int shortestTSPdistance(vector<vector<int> > dist) {
	int n = dist.size();
	int lim = 1 << n;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < lim; ++j)
			dp[j][i] = INF;
	for (int i = 0; i < 1; i++) {
		dp[1 << i][i] = 0;
	}
	for (int mask = 0; mask < lim; mask++) {
		for (int last = 0; last < n; last++) {
			if (mask && (1 << last) == 0) {
				continue;
			}
			for (int curr = 0; curr < n; curr++) {
				if (mask && (1 << curr) == 0) {
					continue;
				}
				int otherMask = mask ^ (1 << curr);
				dp[mask][curr] = min(dp[mask][curr], dp[otherMask][last] + dist[last][curr]);
			}
		}
	}
	int ans = INF;
	for (int i = 0; i < 1; i++) {
		ans = min(ans, dp[lim - 1][i]);
	}
	return ans;
}
int main() {
	int n;
	cin >> n;
	vector <vector<int>> vec;
	for (int i = 0; i < n; ++i) {
		vector <int> temp(3);
		for (int& a : temp)
			cin >> a;
		vec.pb(temp);
	}
	vector <vector<int>> dist;
	for (int i = 0; i < n; ++i) {
		vector <int> temp;
		for (int j = 0; j < n; ++j) {
			temp.pb(abs(vec[i][0] - vec[j][0]) + abs(vec[i][1] - vec[j][1]) + max(0, vec[j][2] - vec[i][2]));
		}
		dist.pb(temp);
	}
	cout << shortestTSPdistance(dist) << endl;
}
#include <bits/stdc++.h>

#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define reset(a, v) memset((a), v, sizeof(a))

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

int n;
pair<ii, int> dat[20];
int dp[20][(1<<17)+5];

int calcDist(pair<ii, int> A, pair<ii, int> B) {
	return abs(A.fi.fi - B.fi.fi) + abs(A.fi.se - B.fi.se) + max(0, B.se - A.se);
}

int DP(int cur, int mask) {
	int& ret = dp[cur][mask];
	if (ret != -1) return ret;
	if (n == __builtin_popcount(mask)) return ret = calcDist(dat[cur], dat[0]);
	ret = INT_MAX;
	for (int nxt = 1; nxt < n; nxt++) {
		if (mask & (1<<nxt)) continue;
		int nxtDist = calcDist(dat[cur], dat[nxt]);
		ret = min(ret, nxtDist + DP(nxt, mask | (1<<nxt)));
	}
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int x, y, z; scanf("%d %d %d", &x, &y, &z);
		dat[i] = {{x,y},z};
	}
	reset(dp,-1);
	printf("%d\n", DP(0, 1));
	return 0;
}