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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;


li res[20];

li n;
PI xy[20];
li po[20];

inline li calc_segment(const vector<PI>& poss, li from, li to) {
    li res = INF;
    repp(i, from, to + 1) {
        li tres = 0;
        repp(j, from, to + 1) {
            tres += abs(poss[j].F - poss[i].F) * poss[j].S;
        }
        res = min(tres, res);
    }
    return res;
}

// calc_dpを正負で分けたやつ
vector<li> calc_dp2(vector<PI>& poss) {
    li nn = sz(poss);

    // table[i][j] : possの区間[i,j]のなかで1本立てるのの最小コスト
    vector<vector<li>> table(nn, vector<li>(nn, INF));
    rep(i, nn) {
        repp(j, i, nn) {
            table[i][j] = calc_segment(poss, i, j);
        }
    }

    // dp[i][j] : i番目まで見てj個作った場合の最小コスト
    vector<vector<li>> dp(nn + 1, vector<li>(nn + 1, INF));

    rep(i, nn + 1) {
        dp[0][i] = 0;
    }
    rep(i, nn) {
        dp[i + 1][0] = dp[i][0] + poss[i].F * poss[i].S;
    }

    repp(i, 1, nn + 1) {
        repp(j, 1, nn + 1) {
            rep(k, i) {
                // kまではj-1本でなんとかしてた場合
                dp[i][j] = min(dp[i][j], dp[k][j - 1] + table[k][i - 1]);
            }
        }
    }

    vector<li> res(nn + 1);
    rep(i, nn + 1) {
        res[i] = dp[nn][i];
    }
    //dump2d(table, nn, nn);
    //dump2d(dp, nn + 1, nn + 1);
    return res;
}

// input: {座標, 人口}
// output: res[i] : i個作った時の最小コスト
vector<li> calc_dp(vector<PI>& poss) {
    vector<PI> pos, neg;
    for (auto && v : poss) {
        if (v.F > 0) {
            pos.pb(v);
        } else if (v.F < 0) {
            neg.pb({ -v.F, v.S});
        }
    }
    sort(allof(pos));
    sort(allof(neg));

    auto dp_pos = calc_dp2(pos);
    auto dp_neg = calc_dp2(neg);
    dp_pos.resize(n + 1, 0);
    dp_neg.resize(n + 1, 0);

    vector<li> res(n + 1, INF);

    rep(i, n + 1) {
        rep(j, n - i + 1) {
            res[i + j] = min(res[i + j], dp_pos[i] + dp_neg[j]);
        }
    }
    return res;
}

inline void process(bitset<22>& bs) {
    vector<PI> xx, yy;
    rin{
        if (bs[i]) {
            xx.pb({xy[i].F, po[i]});
        } else {
            yy.pb({xy[i].S, po[i]});
        }
    }
    auto dx = calc_dp(xx);
    auto dy = calc_dp(yy);

    rep(k, n + 1) {
        rep(j, k + 1) {
            li ny = k - j;
            res[k] = min(res[k], dx[j] + dy[ny]);
        }
    }
}

int main() {
    //vector<PI> poss = {{2, 6}, {5, 9}, {5, 22}};
    //calc_dp2(poss);
    //return 0;
    cin >> n;
    rin{
        cin >> xy[i].F >> xy[i].S >> po[i];
        res[i] = INF;
    }
    res[n] = INF;
    rep(i, bit(n)) {
        bitset<22> bs(i);
        process(bs);
    }


    rep(i, n + 1) {
        cout << res[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 3636