New AtCoder City has an infinite grid of streets, as follows:    * At the center of the city stands a clock tower. Let (0, 0) be the coordinates of this point.   * A straight street, which we will call _East-West Main Street_ , runs east-west and passes the clock tower. It corresponds to the x-axis in the two-dimensional coordinate plane.   * There are also other infinitely many streets parallel to East-West Main Street, with a distance of 1 between them. They correspond to the lines \ldots, y = -2, y = -1, y = 1, y = 2, \ldots in the two-dimensional coordinate plane.   * A straight street, which we will call _North-South Main Street_ , runs north-south and passes the clock tower. It corresponds to the y-axis in the two-dimensional coordinate plane.   * There are also other infinitely many streets parallel to North-South Main Street, with a distance of 1 between them. They correspond to the lines \ldots, x = -2, x = -1, x = 1, x = 2, \ldots in the two-dimensional coordinate plane.  There are N residential areas in New AtCoder City. The i-th area is located at the intersection with the coordinates (X_i, Y_i) and has a population of P_i. Each citizen in the city lives in one of these areas.  **The city currently has only two railroads, stretching infinitely, one along East-West Main Street and the other along North-South Main Street.**   M-kun, the mayor, thinks that they are not enough for the commuters, so he decides to choose K streets and build a railroad stretching infinitely along each of those streets.  Let the _walking distance_ of each citizen be the distance from his/her residential area to the nearest railroad.   M-kun wants to build railroads so that the sum of the walking distances of all citizens, S, is minimized.  For each K = 0, 1, 2, \dots, N, what is the minimum possible value of S after building railroads?
from itertools import product
from bisect import bisect_left


def read():
    N = int(input())
    XYP = []
    for i in range(N):
        x, y, p = map(int, input().split())
        XYP.append((x, y, p))
    return N, XYP



def solve(N, XYP, INF=1<<61):
    
    
    minK = [INF for i in range(N+1)]
    score = 0
    for x, y, p in XYP:
        score += min(abs(x), abs(y)) * p
    minK[0] = score

    for ptn in product(range(3), repeat=N):
        nh = ptn.count(1)
        nv = ptn.count(2)
        k = nh + nv
        # calculate score
        score = 0
        nearest_x = [abs(x)*p for x, y, p in XYP]
        nearest_y = [abs(y)*p for x, y, p in XYP]
        for i in range(N):
            for j in range(N):
                if ptn[j] == 1:
                    nearest_x[i] = min(nearest_x[i], abs(x - XYP[j][0])*p)
                elif ptn[j] == 2:
                    nearest_y[i] = min(nearest_y[i], abs(y - XYP[j][1])*p)
                
        for i in range(N):
            score += min(nearest_x[i], nearest_y[i])
        minK[k] = min(minK[k], score)
    
    for k in range(0, N+1):
        print(minK[k])
    


if __name__ == '__main__':
    inputs = read()
    solve(*inputs)

import sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    N = int(input().strip())
    XYP = np.empty((N, 3), dtype=np.int32)
    for i in range(N):
        XYP[i] = np.fromstring(input().strip(), sep=" ")
    return N, XYP


@njit
def solve(N, XYP, INF=10**18):
    ans = np.full(N+1, INF, dtype=np.int64)
    vcost = np.zeros((2**N, N), dtype=np.int32)
    hcost = np.zeros((2**N, N), dtype=np.int32)

    
    for intptn in range(2**N):
        for i in range(N):
            xi, yi, pi = XYP[i]
            v = abs(xi)
            h = abs(yi)
            for j in range(N):
                xj, yj, pj = XYP[j]
                if (intptn >> j) & 1 == 1:
                    v = min(v, abs(xj-xi))
                    h = min(h, abs(yj-yi))
            vcost[intptn, i] += v
            hcost[intptn, i] += h

    
    for intptn in range(3**N):
        # split into two 2**N pairs
        p, intvptn, inthptn = intptn, 0, 0
        u = 0
        for i in range(N):
            if p % 3 == 1:
                intvptn += 1 << (N-i-1)
                u += 1
            elif p % 3 == 2:
                inthptn += 1 << (N-i-1)
                u += 1
            p //= 3
        s = 0
        for i in range(N):
            s += min(vcost[intvptn, i], hcost[inthptn, i]) * XYP[i, 2]
        ans[u] = min(ans[u], s)
    
    return ans


if __name__ == '__main__':
    inputs = read()
    ans = solve(*inputs)
    for a in ans:
        print(a)
