#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef ll Int;
typedef pair<Int, Int> pii;
typedef pair<Int, double> pid;
typedef pair<double, double> pdd;
typedef pair<Int, pii> pip;
typedef pair<pii, Int> ppi;
typedef pair<double, Int> pdp;
typedef vector<Int> veci;
typedef vector<double> vecd;
typedef vector<Int> veci;
typedef vector<ll> vecll;
typedef vector<double> vecd;
typedef vector<pii> vecpii;
typedef vector<ppi> vecppi;
typedef vector<veci> mati;
typedef vector<vecll> matll;
typedef vector<vecd> matd;
#define A first
#define B second
#define PB(x) push_back(x)
#define EB(x) emplace_back(x)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (x).size()
#define CLR(x) memset(x,0,sizeof x)
#define pdebug() printf("%d\n",__LINE__)
#define REP(i, a, b) for(int i = (a);i <= (b);i++)
#define FORO(i, n) REP(i,0,(int)n-1)
#define FORI(i, n) REP(i,1,(int)n)
#define FORIT(i, t) for(auto i = t.begin();i != t.end();i++)
#define eps 1e-6
#define sqr(x) ((x)*(x))
#define dist(_a, _b) sqrt(sqr(_a.A-_b.A)+sqr(_a.B-_b.B))
#define norm(_a) sqrt(sqr(_a.A)+sqr(_a.B))
#define DUMP(a) do { std::cout << #a " = " << (a) << ", "; } while(false)
#define DUMPLN(a) do { std::cout << #a " = " << (a) << std::endl; } while(false)
template<typename T>
void getMin(T &a, T b) { if (a > b) a = b; }
template<typename T>
void getMax(T &a, T b) { if (a < b) a = b; }
template<typename T>
vector<T> getVector(const int n) { return vector<T>(n); }
template<typename T>
vector<T> getVector(const int n, const T a) { return vector<T>(n, a); }
template<typename T>
vector<T> getEmptyVector() { return vector<T>(); }
template<typename T>
void appendAll(vector<T> &a, vector<T> b) { a.insert(a.end(), b.begin(), b.end()); }
// #define X first
// #define Y second
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const ll MOD = 1000000007;
const int MAXN = 1 << 20;
const ll inf = 1LL << 40LL;
const ll NIL = -inf;
int popcount(int x) { return __builtin_popcount(x); }

int N;
vecppi C;
vecll ans;

ll get_xabs(pii a, pii b) {
    return abs(a.A - b.A);
}

ll get_yabs(pii a, pii b) {
    return abs(a.B - b.B);
}

// 東西大通りの状態がsの場合を解く.
// sのi番目のビットが1 <-> i番目の街に東西方向の鉄道が引く.
void solve(unsigned s) {
    vecll cost(N + 1, inf);
    // cost[i] = 既に引かれている東西方向の鉄道or大通りを使った場合の街iの歩行距離
    FORI(i, N) {
        pii p = C[i].A;
        ll popul = C[i].B;
        cost[i] = popul * min(abs(p.A), abs(p.B));
        FORO(j, N) {
            pii q = C[j + 1].A;
            if((s >> j)&1) {
                getMin(cost[i], get_yabs(p, q) * popul);
            }
        }
    }

    vector<matll> dp(N + 1, matll(N + 1, vecll(N + 1, inf)));
    // dp[i][j][k] = i個の街までに合計でj個の南北方向の鉄道を引いて, 最後に鉄道を引いたのが街kの場合の最小の建設費用.
    dp[0][0][0] = 0;
    FORI(i, N) {
        pii p = C[i].A;
        ll popul = C[i].B;

        // 街iに南北方向の鉄道を引かない
        FORO(j, i + 1) {
            FORO(k, i + 1) {
                pii q = C[k].A;
                getMin(dp[i][j][k], dp[i - 1][j][k] + min(cost[i], popul * get_xabs(p, q)));
            }
        }

        // 街iに南北方向のの鉄道を引く
        FORI(j, i) {
            FORO(k, i) {
                pii q = C[k].A;
                ll scost = 0;
                //街 k + 1...i-1 はx=0,y=0,x=q.A,x=p.Aの近い方の鉄道を使う.
                for(int l = k + 1;l < i;l++) {
                    pii r = C[l].A;
                    scost += min(cost[l], C[l].B * min(get_xabs(r, q), get_xabs(r, p)));
                }
                getMin(dp[i][j][i], dp[k][j - 1][k] + scost);
            }
        }
    }

    int k = popcount(s);
    FORO(i, N + 1) {
        if(k + i > N) break;
        FORO(j, N + 1) {
            getMin(ans[k + i], dp[N][i][j]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    C.resize(N + 1);
    FORI(i, N) cin >> C[i].A.A >> C[i].A.B >> C[i].B;

    C[0].A = pii(-20001, -20001);
    C[0].B = 0;
    sort(ALL(C));

    ans.resize(N + 1, inf);
    FORO(s, (1<<N)) {
        solve(s);
    }

    FORO(i, N + 1) cout << ans[i] << endl;

    return 0;
}

Measured memory_bytes: 3680