// https://atcoder.jp/contests/abc180/tasks/abc180_e

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DEBUG 1
#if DEBUG
  #define _GLIBCXX_DEBUG
  #define DUMP(a) REP(_i, a.size()) cout << a[_i] << (_i + 1 == a.size() ? "\n" : " ")
  #define DUMP2D(b) REP(_j, b.size()) DUMP(b[_j]); cout << endl
#else
  #define DUMP(a)
  #define DUMP2D(b)
#endif

const int N_MAX = 17;
const int X_I_MAX = 1e6;
const int Y_I_MAX = 1e6;
const int Z_I_MAX = 1e6;
const int INF = 1e9;

int N;
vector<int> X;
vector<int> Y;
vector<int> Z;

int S;
vector<vector<int>> d;
vector<vector<int>> dp;

int main() {
  cin >> N;
  X = vector<int>(N);
  Y = vector<int>(N);
  Z = vector<int>(N);
  REP(i, N) cin >> X[i] >> Y[i] >> Z[i];

  d = vector<vector<int>>(N, vector<int>(N));
  REP(v, N) REP(u, N) {
    d[v][u] = abs(X[u] - X[v]) + abs(Y[u] - Y[v]) + max(0, Z[u] - Z[v]);
  }

  S = 1 << N;
  dp = vector<vector<int>>(S, vector<int>(N, INF));
  dp[S - 1][0] = 0;

  for (int s = S - 2; s >= 0; s--) {
    REP(v, N) REP(u, N) if (!(s >> u & 1)){
      dp[s][v] = min(dp[s][v], d[v][u] + dp[s | 1 << u][u]);
    }
    REP(v, N) REP(u, N) if (s >> u & 1){
      dp[s][v] = min(dp[s][v], d[v][u] + dp[s][u]);
    }
  }

  int ans = dp[0][0];
  cout << ans << endl;
}

#include <bits/stdc++.h>
using namespace std;

template <class A, class B> bool cmin(A& a, B b) { return a > b && (a = b, true); }
template <class A, class B> bool cmax(A& a, B b) { return a < b && (a = b, true); }

template <typename T> class Dinic {
public:
  static_assert(std::is_integral<T>::value, "Integral required.");
  struct edge {
    int to;
    T cap;
    int rev;
  };

private:
  const int V;
  T max_cap;
  vector<int> level, iter, que;
  static unsigned long long floor2(unsigned long long v) {
    v = v | (v >> 1), v = v | (v >> 2);
    v = v | (v >> 4), v = v | (v >> 8);
    v = v | (v >> 16), v = v | (v >> 32);
    return v - (v >> 1);
  }
  void bfs(const int s, const T base) {
    fill(level.begin(), level.end(), -1);
    level[s] = 0;
    int qh = 0, qt = 0;
    for (que[qt++] = s; qh < qt;) {
      int v = que[qh++];
      for (edge& e : G[v]) {
        if (level[e.to] < 0 && e.cap >= base) {
          level[e.to] = level[v] + 1;
          que[qt++] = e.to;
        }
      }
    }
  }
  T dfs(const int v, const int t, const T base, const T f) {
    if (v == t) return f;
    T sum = 0;
    for (int& i = iter[v]; i < (int)G[v].size(); i++) {
      edge& e = G[v][i];
      if (e.cap >= base && level[v] < level[e.to]) {
        T d = dfs(e.to, t, base, min(f - sum, e.cap));
        if (d > 0) {
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          sum += d;
          if (f - sum < base) break;
        }
      }
    }
    return sum;
  }

public:
  vector<vector<edge> > G;

  Dinic(const int node_size) : V(node_size), max_cap(0), level(V), iter(V), que(V), G(V) {}
  void add(const int from, const int to, const T cap) {
    G[from].push_back((edge){to, cap, (int)G[to].size()});
    G[to].push_back((edge){from, (T)0, (int)G[from].size() - 1});
    max_cap = max(max_cap, cap);
  }
  T solve(const int s, const int t) {
    T flow = 0;
    for (T base = floor2(max_cap); base >= 1;) {
      bfs(s, base);
      if (level[t] < 0) {
        base >>= 1;
        continue;
      }
      fill(iter.begin(), iter.end(), 0);
      flow += dfs(s, t, base, numeric_limits<T>::max());
    }
    return flow;
  }
};

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int N;
  cin >> N;
  int MX = N + 4e5 + 2;
  Dinic<int> D(MX);
  for (int i = 0; i < N; i++) {
    D.add(MX - 2, i, 1);
    int a, b;
    cin >> a >> b, a--, b--;
    D.add(i, N + a, 1);
    D.add(i, N + b, 1);
  }
  for (int i = 0; i < 4e5; i++) {
    D.add(N + i, MX - 1, 1);
  }
  cout << D.solve(MX - 2, MX - 1) << '\n';
}