//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}



//head



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vi x(n), y(n), z(n);
  rep(i, n) cin >> x[i] >> y[i] >> z[i];
  vvi dist(n, vi(n));
  rep(i, n) {
    rep(j, n) {
      int u = abs(x[i]-x[j]) + abs(y[i]-y[j]) + max(0, z[j]-z[i]);
      dist[i][j] = u;
    }
  }
  vvi dp(1<<n, vi(n, INT_MAX));
  dp[1][0] = 0;
  for(int i = 1; i < (1<<n)-1; i++) {
    rep(j, n) if((i>>j&1) and dp[i][j] != INT_MAX) {
      int now = dp[i][j];
      rep(k, n) if(~i>>k&1) {
        chmin(dp[i|(1<<k)][k], now+dist[j][k]);
      }
    }
  }
  int ans = INT_MAX;
  for(int i = 1; i < n; i++) {
    chmin(ans, dp[(1<<n)-1][i]+dist[i][0]);
  }
  cout << ans << endl;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <limits>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
template<class T> inline int  sz(T &a) { return a.size(); }
using ll = long long; using ld = long double;
using pi = pair<int,int>; using pl = pair<ll,ll>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
const int inf = numeric_limits<int>::max();
const ll infll = numeric_limits<ll>::max();
//****************************************
// Graph template
//****************************************

// status of edge
template <typename X>
struct Edge{
  int from;
  int to;
  X cost;

  Edge() = default;

  Edge(int from, int to, X cost) : from(from), to(to), cost(cost) {}
};

// status of node
template <typename X>
struct Node{ 
  int idx;
  vector<Edge<X>> edge;
  
  Node() = default;

  explicit Node(int idx) : idx(idx) {}
};

template <typename X>
class Graph{
private:
  int n; // number of node
  int m; // number of edge
  vector<Node<X>> node; 

  void Init_Node() {
    rep(i,n) node.emplace_back(i);
  }
public:
  explicit Graph(int n) : n(n) {
    Init_Node();
  }

  // edges have no-weight 
  Graph(int n, int m, vector<int> from, vector<int> to) : n(n), m(m) {
    Init_Node();
    rep(i,m) {
      add_edge(from[i], to[i]);
      add_edge(to[i], from[i]);      
    }
  }  

  // edges have weight
  Graph(int n, int m, vector<int> from, vector<int> to, vector<X> cost) : n(n), m(m) {
    Init_Node();
    rep(i,m) {
      add_edge(from[i], to[i], cost[i]);
      add_edge(to[i], from[i], cost[i]);      
    }
  }

  void add_edge(int from, int to, X cost = 1) {
    node[from].edge.emplace_back(from, to, cost);
  }


  void Solve() {
    vi d(n, -1);
    d[0] = 0;
    auto dfs = [&](auto self, int v)->void{
      for(auto next: node[v].edge) {
	int w = next.to;
	if(d[w] != -1) continue;
	if(d[v] == next.cost) {
	  d[w] = (d[v] + 1) % n;
	  self(self, w);
	}
	else {
	  d[w] = next.cost;
	  self(self, w);	  
	}
      }
    };
    dfs(dfs, 0);
    rep(i,n) cout << d[i]+1 << "\n";
  }
  
};


int main()
{
  int n,m; cin >> n >> m;
  vi a(m),b(m),c(m);
  rep(i,m) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--; b[i]--; c[i]--;
  }

  Graph<int> gp(n, m, a, b, c);
  gp.Solve();
  
  return 0;
}
