// #pragma GCC optimize("Ofast")

#include <vector>
#include <iostream>
#include <utility>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>
#include <string>
#include <utility>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> pii;
// #define int ll
#define fi first
#define se second
#define Sort(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; ++i) 
#define REP(i,n) for(int i = 0;i < (n) ; ++i) 
#define MP(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define INF LLONG_MAX/4
#define INTINF INT_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
template<class T> inline bool chmax(T &a, T b){if(a < b){a = b;return true;}return false;}
template<class T> inline bool chmin(T &a, T b){if(a > b){a = b;return true;}return false;}
/*----------------------------------------------------------------*/
inline unsigned long long xor128() {
	static unsigned long long rx = 123456789, ry = 986960440, rz = 738905609, rw = 23140692;
	unsigned long long rt = (rx ^ (rx << 11));
	rx = ry;ry = rz;rz = rw;
	return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
}
inline float rand128(float min = 0, float max = 1){
	return (float)(xor128() % 0xFFFF) / 0xFFFF * (max - min) + min;
}

inline uint64_t rdtsc(){
	uint32_t hi,lo;
	__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
	return ((uint64_t)lo) | (((uint64_t)hi)<<32);
}
inline double GetSeconds() {
	// return rdtsc()/2.8e9; //Topcoder
	return rdtsc()/3.0e9; // Atcoder
}
double start_time;
const double TL = 1.90;
/*----------------------------------------------------------------*/

/*----------------------------------------------------------------*/
int h[30][29];
int v[29][30];

const int Q = 1000;
const int H = 30;
const int W = 30;

/*----------------------------------------------------------------*/
void input(){
	cerr << "in h" << endl;
	cerr << H << endl;
	cerr << W << endl;
	rep(i,H)rep(j,W-1){
		cin >> h[i][j];
		cerr << h[i][j] << endl;
	}
	cerr << "in v" << endl;
	rep(i,H-1)rep(j,W)cin >> v[i][j];
}   

void solve(){
	cerr << "solve" << endl;
    int si,sj,ti,tj,a;
	rep(q,Q){
        cin >> si >> sj >> ti >> tj;
        if(si > ti)rep(i,si-ti)cout << 'U';
        if(ti > si)rep(i,ti-si)cout << 'D';
        if(sj > tj)rep(i,sj-tj)cout << 'L';
        if(tj > sj)rep(i,tj-sj)cout << 'R';
        cout << endl;
        cin >> a;
    }
}

/*----------------------------------------------------------------*/

int main(){
	cerr << "s" << endl;
	start_time = GetSeconds();
	solve();
}
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

vector<int> x, y, z;

int dis(int j, int k){
    
    return abs(x[j] - x[k]) + abs(y[j] - y[k]) + max(0ll, z[k] - z[j]);
}

signed main(){
	cout<<fixed<<setprecision(10);
	
    int N, M;
	vector<vector<int>> dp;
	cin>>N;
    
    dp.resize(N, vector<int>(1<<N, INF));
	
    x.resize(N);
    y.resize(N);
    z.resize(N);
    
    for(int i = 0; i < N; i++){
        cin>>x[i]>>y[i]>>z[i];
    }
    
    dp[0][0] = 0;
    
    for(int i = 1; i < 1<<N; i++){
        for(int j = 0; j < N; j++){
            for(int k = 0; k < N; k++){
                if(!((i>>k)&1)) continue;
                
                dp[k][i] = min(dp[k][i|(1<<k)], dp[j][i^(1<<k)] + dis(j, k));
            }
        }
    }
    
    cout<<dp[0][(1<<N)-1]<<endl;
    
	return 0;
}