#include<bits/stdc++.h>
 
#define ll long long
 
using namespace std;
//memset(dp, 0, sizeof(dp));
 
vector<int> l(200005);
unordered_map<int, unordered_map<int, int>> h;
int n, m;
 
void dfs(int c) {
	for(auto &i : h[c]) {
		if(l[i.first] > 0) {
			continue;
		}
		if(i.second == l[c]) {
			l[i.first] = l[c] % n + 1;
			dfs(i.first);
		} else {
			l[i.first] = i.second;
			dfs(i.first);
		}
	}
}
 
void work(int T) {
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		h[v][u] = c;
		h[u][v] = c;
	}
	l[1] = 1;
	dfs(1);
	for(int i = 1; i <= n; i++) {
		cout << l[i] << endl;
	}
}
 
int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
	// int t;
	// for(cin >> t; t > 0; t--) {
		// work(t);
	// }
	work(0);
	
	return 0;
};
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    int n, x, y, z;;
    cin >> n;
    vector<array<ll, 3>> pts;
    for(int i = 0; i < n; i++) {
        cin >> x >> y >> z;
        pts.push_back({x, y, z});
    }
    vector<vector<ll>> cost(n, vector<ll>(n, 0));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cost[i][j] = llabs(pts[j][0] - pts[i][0]) + 
                llabs(pts[j][1] - pts[i][1]) + 
                max(pts[j][2]-pts[i][2], 0LL);
        }
    }
    int mx_state = 1 << n;
    vector<vector<ll>> dp(mx_state, vector<ll>(n, INT_MAX/2));
    for(int i = 0; i < n; i++) {
        dp[1<<i][i] = cost[0][i];
    }
    for(int s = 0; s < mx_state; s++) {
        for(int dst = 0; dst < n; dst++) {
            if (s >> dst & 1) {
                int state0  = s ^ (1<<dst);
                for(int src = 0; src < n; src++) {
                    if (state0 >> src & 1) {
                        ll cand = dp[state0][src] + cost[src][dst];
                        if (cand < dp[s][dst]) {
                            dp[s][dst] = cand;
                        }
                    }
                }
            }
        }
    }
    ll ans = INT_MAX;
    for(int i = 0; i < n; i++)
        ans = min(ans, dp[(1<<n)-1][i] + cost[i][0]);
    cout << ans << endl;
    return 0;
}
