import sys

import numpy as np



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



def main(XYP):

    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]

    N = len(X)

    dp_X = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト

    dp_X[0] = np.abs(X) * P

    for n in range(N):

        B = 1 << n

        dp_X[B:2 * B] = np.minimum(dp_X[:B], np.abs(X - X[n]) * P)



    dp_Y = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト

    dp_Y[0] = np.abs(Y) * P

    for n in range(N):

        B = 1 << n

        dp_Y[B:2 * B] = np.minimum(dp_Y[:B], np.abs(Y - Y[n]) * P)



    popcount = np.zeros(1 << N, np.int64)

    for n in range(N):

        popcount[1 << n:1 << n + 1] = popcount[:1 << n] + 1



    INF = 10**18

    ans = np.full(N + 1, INF, np.int64)

    for s in range(1 << N):

        size = popcount[s]

        t = s

        while True:

            u = s ^ t

            cost = (np.minimum(dp_X[t], dp_Y[u])).sum()

            ans[size] = min(ans[size], cost)

            if t == 0:

                break

            t = (t - 1) & s

    return ans



if sys.argv[-1] == 'ONLINE_JUDGE':

    import numba

    from numba.pycc import CC

    i8 = numba.int64

    cc = CC('my_module')



    def cc_export(f, signature):

        cc.export(f.__name__, signature)(f)

        return numba.njit(f)



    main = cc_export(main, (i8[:], ))

    cc.compile()



from my_module import main



N = int(readline())

XYP = np.array(read().split(), np.int64)



ans = main(XYP)

print(('\n'.join(map(str, ans.tolist()))))
import sys

import numpy as np

import numba

from numba import njit

i8 = numba.int64



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



@njit((i8[:], i8[:]), cache=True)

def f(X, P):

    INF = 10**18

    ind = np.argsort(X)

    X, P = X[ind], P[ind]

    N = len(X)

    if N == 0:

        return np.array([0], np.int64)

    # [0, i) から X[j] までのコストの和

    dp1 = np.zeros((N + 1, N), np.int64)

    for i in range(N):

        for j in range(N):

            dp1[i + 1, j] = np.abs(X[i] - X[j]) * P[i]

    for i in range(N):

        dp1[i + 1] += dp1[i]



    # [l, r]をひとまとめにするときのコストの最小値

    dp2 = np.empty((N, N), np.int64)

    for l in range(N):

        for r in range(l, N):

            dp2[l, r] = (dp1[r + 1] - dp1[l]).min()



    # [0,i] を j 件でとる場合のコストの最小値

    dp3 = np.full((N, N + 1), INF, np.int64)

    for i in range(N):

        dp3[i, 0] = np.sum(X[:i + 1] * P[:i + 1])

        dp3[i, 1] = dp2[0, i]

        for j in range(i):

            # [0,j] + (j,i]

            dp3[i, 1:] = np.minimum(dp3[i, 1:], dp3[j, :-1] + dp2[j + 1, i])

    return dp3[-1]



@njit((i8[:], i8[:]), cache=True)

def merge(A, B):

    LA, LB = len(A), len(B)

    INF = 10**18

    C = np.full(LA + LB - 1, INF, np.int64)

    for i in range(LA):

        C[i:i + LB] = np.minimum(C[i:i + LB], A[i] + B)

    return C



@njit((i8[:], ), cache=True)

def main(XYP):

    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]

    N = len(X)

    INF = 10**18

    ans = np.full(N + 1, INF, np.int64)

    full = (1 << N) - 1

    for x in range(1 << N):

        i_x = np.bool_([x & (1 << i) for i in range(N)])

        i_y = ~i_x

        dp = f(X[i_x & (X >= 0)], P[i_x & (X >= 0)])

        dp = merge(dp, f(-X[i_x & (X < 0)], P[i_x & (X < 0)]))

        dp = merge(dp, f(Y[i_y & (Y >= 0)], P[i_y & (Y >= 0)]))

        dp = merge(dp, f(-Y[i_y & (Y < 0)], P[i_y & (Y < 0)]))

        ans = np.minimum(ans, dp)

    return ans



N = int(readline())

XYP = np.array(read().split(), np.int64)



ans = main(XYP)

print(('\n'.join(map(str, ans.tolist()))))
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main(XYP):
    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
    N = len(X)
    dp_X = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト
    dp_X[0] = np.abs(X) * P
    for n in range(N):
        B = 1 << n
        dp_X[B : 2 * B] = np.minimum(dp_X[:B], np.abs(X - X[n]) * P)
    dp_Y = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト
    dp_Y[0] = np.abs(Y) * P
    for n in range(N):
        B = 1 << n
        dp_Y[B : 2 * B] = np.minimum(dp_Y[:B], np.abs(Y - Y[n]) * P)
    popcount = np.zeros(1 << N, np.int64)
    for n in range(N):
        popcount[1 << n : 1 << n + 1] = popcount[: 1 << n] + 1
    INF = 10**18
    ans = np.full(N + 1, INF, np.int64)
    for s in range(1 << N):
        size = popcount[s]
        t = s
        while True:
            u = s ^ t
            cost = (np.minimum(dp_X[t], dp_Y[u])).sum()
            ans[size] = min(ans[size], cost)
            if t == 0:
                break
            t = (t - 1) & s
    return ans


if sys.argv[-1] == "ONLINE_JUDGE":
    import numba
    from numba.pycc import CC

    i8 = numba.int64
    cc = CC("my_module")

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i8[:],))
    cc.compile()
from my_module import main

N = int(readline())
XYP = np.array(read().split(), np.int64)
ans = main(XYP)
print(("\n".join(map(str, ans.tolist()))))

import sys
import numpy as np
import numba
from numba import njit

i8 = numba.int64
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


@njit((i8[:], i8[:]), cache=True)
def f(X, P):
    INF = 10**18
    ind = np.argsort(X)
    X, P = X[ind], P[ind]
    N = len(X)
    if N == 0:
        return np.array([0], np.int64)
    # [0, i) から X[j] までのコストの和
    dp1 = np.zeros((N + 1, N), np.int64)
    for i in range(N):
        for j in range(N):
            dp1[i + 1, j] = np.abs(X[i] - X[j]) * P[i]
    for i in range(N):
        dp1[i + 1] += dp1[i]
    # [l, r]をひとまとめにするときのコストの最小値
    dp2 = np.empty((N, N), np.int64)
    for l in range(N):
        for r in range(l, N):
            dp2[l, r] = (dp1[r + 1] - dp1[l]).min()
    # [0,i] を j 件でとる場合のコストの最小値
    dp3 = np.full((N, N + 1), INF, np.int64)
    for i in range(N):
        dp3[i, 0] = np.sum(X[: i + 1] * P[: i + 1])
        dp3[i, 1] = dp2[0, i]
        for j in range(i):
            # [0,j] + (j,i]
            dp3[i, 1:] = np.minimum(dp3[i, 1:], dp3[j, :-1] + dp2[j + 1, i])
    return dp3[-1]


@njit((i8[:], i8[:]), cache=True)
def merge(A, B):
    LA, LB = len(A), len(B)
    INF = 10**18
    C = np.full(LA + LB - 1, INF, np.int64)
    for i in range(LA):
        C[i : i + LB] = np.minimum(C[i : i + LB], A[i] + B)
    return C


@njit((i8[:],), cache=True)
def main(XYP):
    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
    N = len(X)
    INF = 10**18
    ans = np.full(N + 1, INF, np.int64)
    full = (1 << N) - 1
    for x in range(1 << N):
        i_x = np.bool_([x & (1 << i) for i in range(N)])
        i_y = ~i_x
        dp = f(X[i_x & (X >= 0)], P[i_x & (X >= 0)])
        dp = merge(dp, f(-X[i_x & (X < 0)], P[i_x & (X < 0)]))
        dp = merge(dp, f(Y[i_y & (Y >= 0)], P[i_y & (Y >= 0)]))
        dp = merge(dp, f(-Y[i_y & (Y < 0)], P[i_y & (Y < 0)]))
        ans = np.minimum(ans, dp)
    return ans


N = int(readline())
XYP = np.array(read().split(), np.int64)
ans = main(XYP)
print(("\n".join(map(str, ans.tolist()))))

+import numba +from numba import njit +i8 = numba.int64 +@njit((i8[:], i8[:]), cache=True) +def f(X, P): +    INF = 10**18 +    ind = np.argsort(X) +    X, P = X[ind], P[ind] +    N = len(X) +    if N == 0: +        return np.array([0], np.int64) +    # [0, i) から X[j] までのコストの和 +    dp1 = np.zeros((N + 1, N), np.int64) +    for i in range(N): +        for j in range(N): +            dp1[i + 1, j] = np.abs(X[i] - X[j]) * P[i] +    for i in range(N): +        dp1[i + 1] += dp1[i] +    # [l, r]をひとまとめにするときのコストの最小値 +    dp2 = np.empty((N, N), np.int64) +    for l in range(N): +        for r in range(l, N): +            dp2[l, r] = (dp1[r + 1] - dp1[l]).min() +    # [0,i] を j 件でとる場合のコストの最小値 +    dp3 = np.full((N, N + 1), INF, np.int64) +    for i in range(N): +        dp3[i, 0] = np.sum(X[: i + 1] * P[: i + 1]) +        dp3[i, 1] = dp2[0, i] +        for j in range(i): +            # [0,j] + (j,i] +            dp3[i, 1:] = np.minimum(dp3[i, 1:], dp3[j, :-1] + dp2[j + 1, i]) +    return dp3[-1] + + +@njit((i8[:], i8[:]), cache=True) +def merge(A, B): +    LA, LB = len(A), len(B) +    INF = 10**18 +    C = np.full(LA + LB - 1, INF, np.int64) +    for i in range(LA): +        C[i : i + LB] = np.minimum(C[i : i + LB], A[i] + B) +    return C + + +@njit((i8[:],), cache=True) -    dp_X = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト -    dp_X[0] = np.abs(X) * P -    for n in range(N): -        B = 1 << n -        dp_X[B : 2 * B] = np.minimum(dp_X[:B], np.abs(X - X[n]) * P) -    dp_Y = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト -    dp_Y[0] = np.abs(Y) * P -    for n in range(N): -        B = 1 << n -        dp_Y[B : 2 * B] = np.minimum(dp_Y[:B], np.abs(Y - Y[n]) * P) -    popcount = np.zeros(1 << N, np.int64) -    for n in range(N): -        popcount[1 << n : 1 << n + 1] = popcount[: 1 << n] + 1 -    for s in range(1 << N): -        size = popcount[s] -        t = s -        while True: -            u = s ^ t -            cost = (np.minimum(dp_X[t], dp_Y[u])).sum() -            ans[size] = min(ans[size], cost) -            if t == 0: -                break -            t = (t - 1) & s +    full = (1 << N) - 1 +    for x in range(1 << N): +        i_x = np.bool_([x & (1 << i) for i in range(N)]) +        i_y = ~i_x +        dp = f(X[i_x & (X >= 0)], P[i_x & (X >= 0)]) +        dp = merge(dp, f(-X[i_x & (X < 0)], P[i_x & (X < 0)])) +        dp = merge(dp, f(Y[i_y & (Y >= 0)], P[i_y & (Y >= 0)])) +        dp = merge(dp, f(-Y[i_y & (Y < 0)], P[i_y & (Y < 0)])) +        ans = np.minimum(ans, dp) - -if sys.argv[-1] == "ONLINE_JUDGE": -    import numba -    from numba.pycc import CC - -    i8 = numba.int64 -    cc = CC("my_module") - -    def cc_export(f, signature): -        cc.export(f.__name__, signature)(f) -        return numba.njit(f) - -    main = cc_export(main, (i8[:],)) -    cc.compile() -from my_module import main