#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#define PI 3.14159265359
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pai;
typedef pair<ll, ll> pal;
const int INF = 1e9+7;
const int MOD = 1e9+7;
const int MODD = 998244353;
const ll LLINF = 1e18;
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)

template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

int V;
int G[20][20];  // グラフ
int dp[200000][20];
// メモ化再帰
int rec(int S, int v) {  
    if (S == 0) {
        if (v == 0) {
            return 0;
        } else {
            return INF;
        }
    }
    if ((S & (1 << v)) == 0) {  // Sに{v}が含まれていない
        return INF;
    }
    int &ret = dp[S][v];
    if (ret != 0) return ret;
    ret = INF;
    REP(u, V) { chmin(ret, rec(S ^ (1 << v), u) + G[u][v]); }
    return ret;
}

int main() {
    cin >> V;
    // グラフの初期化
    REP(i, 20) {
        REP(j, 20) { G[i][j] = INF; }
    }
    int x[20], y[20], z[20];
    for (int i = 0; i < V; i++){
    	cin >> x[i] >> y[i] >> z[i];
    }
    for (int i = 0; i < V; i++){
    	for (int j = 0; j < V; j++){
    		G[i][j] = abs(x[j] - x[i]) + abs(y[j] - y[i]) + max(0, z[j] - z[i]);
    	}
    }
    int ans = rec((1 << V) - 1, 0);
    if (ans != INF) {
        cout << ans << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
#define MOD 1000000007
#define dd double
#define vi vector<int>
#define vll vector<ll>
#define forr(i,n) for(ll i=0;i<n;i++)
#define revf(i,n) for(ll i=n-1;i>=0;i--)
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep1(i,b) for(ll i=1;i<=b;i++)
#define inp(a,n) for(ll i=0;i<n;i++)cin>>a[i]
#define outp(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" "
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (((a)*(b))/gcd((a),(b)))
#define pb push_back
#define mp make_pair
#define BINSC binary_search
#define BITOUT __builtin_popcount
#define mem(x,n) memset(x,n,sizeof(x))
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define test ll t; cin>>t; while(t--)
#define cn cout<<"\n";
int main()
{
     fast
     ll x,y,z;
     cin>>x>>y>>z;
     double a=(dd)y/x;
     dd b=a*z;
     if(floor(b)==ceil(b))
     cout<<b-1;
     else
     cout<<floor(b);
}