#pragma GCC target("avx2")
#pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

using namespace std;
constexpr int INF = 168430090;
int x[17], y[17], z[17], dist[17][17], dp[17][131072];



int main()
{
    memset(dp, 10, sizeof(dp));
	dp[0][1] = 0;
	int N; scanf("%d", &N);
	for(int i = 0; i < N; i++)scanf("%d%d%d", &x[i], &y[i], &z[i]);
	int NUM = (1<<N);

	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			dist[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]) + max(0, z[j] - z[i]);
		}
	}


	for(int bit = 1; bit < NUM; bit++) {
		for(int i = 0; i < N; i++) {
			if(!((1<<i) & bit) || dp[i][bit] == INF)continue;
			for(int j = 0; j < N; j++) {
				if((1<<j) & bit)continue;
				dp[j][bit | (1<<j)] = min(dp[j][bit | (1<<j)], dp[i][bit] + dist[i][j]);
			}
		}
	}

	int ans = INF;
	while(--N) {
		ans = min(ans, dp[N][NUM - 1] + dist[N][0]);
	}
	printf("%d\n", ans);
}
#include<bits/stdc++.h>
using namespace std;
long int min=-1;
void find_min(long int m)
{
  if(::min==-1)
  {
    ::min=m;
    return;
  }
  if(m<(::min))
    ::min=m;
}
int main()
{
  long int n,**a,i;
  cin>>n;
  a=new long int*[n];
  for(i=0;i<n;i++)
  {
    a[i]=new long int[3];
    cin>>a[i][0]>>a[i][1]>>a[i][2];
    if(a[i][2]-a[i][0]>0)
      find_min(a[i][1]);
  }
  cout<<::min<<endl;
  return 0;
}