#include <bits/stdc++.h>

#define ll long long
#define X first
#define Y second
#define pii pair<int,int>
#define ld long long double
using namespace std;
int const N = 18;
int x[N], y[N], z[N];
int target;
ll oo = 1e16;
int n;
ll mem[N][1<<18];
ll cal(int i, int j){
    return abs(x[i] - x[j]) + abs(y[i]-y[j]) + max(0, z[j]-z[i]);
}
ll dp(int nd, int mask){
    if((mask&target) == target){
        return cal(nd, 0);
    }
    ll &ret = mem[nd][mask];
    if(~ret)
        return ret;
    ret = oo;
    for(int i=0; i<n; i++){
        if((mask & (1<<i)) == 0){
            ret = min(ret, dp(i, mask | (1<<i)) + cal(nd, i));
        }
    }
    return ret;
}

void test() {
    memset(mem, -1, sizeof(mem));
    cin>>n;
    target = (1<<n) - 1;
    for(int i=0; i<n; i++){
        cin>>x[i]>>y[i]>>z[i];
    }
    cout<<dp(0, 1)<<'\n';
}

int main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false), cin.tie(0);
#endif
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
        test();
    }

}
#include "bits/stdc++.h"
//#include "atcoder/all"
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
#define endl "\n"
vector<bool>B(100005);
vector<bool>B2(100005);
vector<int>Ans(100005);
struct Edge {
	int to, id;
	Edge(int to, int id) :to(to), id(id) {}
};
vector<Edge>g[100005];
vector<Edge>g2[100005];

void dfs(int v, int p = -1) {
	if (B[v]) {
		return;
	}
	B[v] = true;
	for (Edge e : g[v]) {
		if (p == e.to) {
			continue;
		}
		if (B[e.to]) {
			continue;
		}
		g2[v].emplace_back(e.to, e.id);
		dfs(e.to, v);
	}
	return;
}

void dfs2(int v, int id = -1, int p = -1) {
	Ans[v] = id;
	if (-1 != id) {
		B2[id] = true;
	}
	for (Edge e : g2[v]) {
		if (p == e.to) {
			continue;
		}
		if (Ans[v] != e.id) {
			dfs2(e.to, e.id, v);
		}
		else {
			dfs2(e.to, -1, v);
		}
	}
	return;
}

int main() {
	int N, M;
	cin >> N >> M;
	for (int n = 0; n < M; ++n) {
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		c--;
		g[a].emplace_back(b, c);
		g[b].emplace_back(a, c);
	}
	for (int i = 0; i < N; ++i) {
		B[i] = false;
		B2[i] = false;
	}
	dfs(0);
	dfs2(0);
	int memo = 0;
	for (; memo < N; ++memo) {
		if (!B2[memo]) {
			break;
		}
	}
	for (int n = 0; n < N; ++n) {
		if (-1 == Ans[n]) {
			Ans[n] = memo;
		}
		cout << Ans[n] + 1 << endl;
	}
	return 0;
}