#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

void f(vector<int> &X, vector<int> &P, vector<long long> &A)
{
    int n = (int)X.size();

    {
        static vector<pair<int, int>> T;
        T.clear();
        for (int i=0; i<n; i++)
            T.push_back(make_pair(X[i], P[i]));
        sort(T.begin(), T.end());
        for (int i=0; i<n; i++)
            X[i] = T[i].first,
            P[i] = T[i].second;
    }

    //  C[begin][end]
    static vector<vector<long long>> C;
    C.resize(n+1);
    for (auto &c: C)
    {
        c.clear();
        c.resize(n+1);
    }
    for (int b=0; b<n; b++)
    for (int e=b; e<n; e++)
    {
        int S = 0;
        for (int i=b; i<=e; i++)
            S -= P[i];
        for (int i=b; i<=e; i++)
        {
            if (S+P[i]*2>=0)
            {
                C[b][e] = 0;
                for (int j=b; j<=e; j++)
                    C[b][e] += (long long)abs(X[i]-X[j])*P[j];
                break;
            }
            S += P[i]*2;
        }
    }

    //  T[lines][cities]
    static vector<vector<long long>> T;
    T.resize(n+1);
    for (auto &t: T)
    {
        t.clear();
        t.resize(n+1, 999999999999LL);
    }

    T[0][0] = 0;
    for (int i=0; i<n; i++)
        T[0][i+1] = T[0][i]+(long long)X[i]*P[i];
    for (int i=1; i<=n; i++)
    {
        T[i][0] = 0;
        for (int j=1; j<=n; j++)
            for (int k=0; k<j; k++)
                T[i][j] = min(T[i][j], T[i-1][k]+C[k][j-1]);
    }

    for (int i=0; i<=n; i++)
        A[i] = T[i][n];
    for (int i=n+1; i<(int)A.size(); i++)
        A[i] = 0;
}

int main()
{
    int N;
    cin>>N;
    vector<int> X(N), Y(N), P(N);
    for (int i=0; i<N; i++)
        cin>>X[i]>>Y[i]>>P[i];

    vector<long long> ans(N+1, 999999999999LL);
    vector<int> XN, XP, YN, YP;
    vector<int> XNP, XPP, YNP, YPP;
    vector<long long> XNA(N+1), XPA(N+1), YNA(N+1), YPA(N+1);

    for (int b=0; b<1<<N; b++)
    {
        XN.clear();
        XP.clear();
        YN.clear();
        YP.clear();
        XNP.clear();
        XPP.clear();
        YNP.clear();
        YPP.clear();

        for (int i=0; i<N; i++)
        {
            if (b>>i&1)
            {
                if (X[i]<0)
                    XN.push_back(-X[i]),
                    XNP.push_back(P[i]);
                if (X[i]>0)
                    XP.push_back(X[i]),
                    XPP.push_back(P[i]);
            }
            else
            {
                if (Y[i]<0)
                    YN.push_back(-Y[i]),
                    YNP.push_back(P[i]);
                if (Y[i]>0)
                    YP.push_back(Y[i]),
                    YPP.push_back(P[i]);
            }
        }

        f(XN, XNP, XNA);
        f(XP, XPP, XPA);
        f(YN, YNP, YNA);
        f(YP, YPP, YPA);

        for (int xn=0; xn<=N; xn++)
        for (int xp=0; xn+xp<=N; xp++)
        for (int yn=0; xn+xp+yn<=N; yn++)
        for (int yp=0; xn+xp+yn+yp<=N; yp++)
        {
            int K = xn+xp+yn+yp;
            ans[K] = min(ans[K], XNA[xn]+XPA[xp]+YNA[yn]+YPA[yp]);
        }
    }
    for (int K=0; K<=N; K++)
        cout<<ans[K]<<endl;
}


Measured memory_bytes: 3192