local mmi, mma = math.min, math.max
local mab = math.abs
local mfl, mce = math.floor, math.ceil
local bls, brs = bit.lshift, bit.rshift
local bxor = bit.bxor

local n = io.read("*n")
local x, y, p = {}, {}, {}
local flag = {}
for i = 1, n do
  x[i], y[i], p[i] = io.read("*n", "*n", "*n")
end

local tot = 1
for i = 1, n do
  tot = tot * 3
end
local tot2 = bls(1, n)
local xlen, ylen = {}, {}
for i = 1, n do
  xlen[i] = {}
  ylen[i] = {}
  for j = 0, tot2 - 1 do
    local candx, candy = mab(x[i]), mab(y[i])
    local tj = j
    for k = 1, n do
      if tj % 2 == 1 then
        candx = mmi(candx, mab(x[i] - x[k]))
        candy = mmi(candy, mab(y[i] - y[k]))
      end
      tj = brs(tj, 1)
    end
    xlen[i][j + 1] = candx * p[i]
    ylen[i][j + 1] = candy * p[i]
  end
end
local box = {}
local rettbl = {}
for i = 1, n do
  rettbl[i] = 10000 * 1000000 * 15 + 1
end
rettbl[n + 1] = 0

local tmpx, tmpy = {}, {}
local tmpe = {}
for i = 0, 59048 do -- 3^10 = 59049
  local ti = i
  local mul = 1
  local tbl = {}
  local xv, yv = 0, 0
  for j = 1, 10 do
    local z = ti % 3
    if z == 0 then
      table.insert(tbl, j)
    elseif z == 1 then
      xv = xv + mul
    elseif z == 2 then
      yv = yv + mul
    end
    mul = mul * 2
    ti = mfl(ti / 3)
  end
  tmpx[i + 1] = xv
  tmpy[i + 1] = yv
  tmpe[i + 1] = tbl
end

for i = 0, tot - 1 do
  local ti = i
  local ecnt = 0
  local mul = 1
  local xv, yv = 0, 0
  local ofst = 0
  local rep = mfl(n / 10)
  for irep = 1, rep do
    local tti = ti % 59049
    xv = xv + mul * tmpx[tti + 1]
    yv = yv + mul * tmpy[tti + 1]
    for k = 1, #tmpe[tti + 1] do
      local z = ofst + tmpe[tti + 1][k]
      if z <= n then
        ecnt = ecnt + 1
        box[ecnt] = z
      end
    end
    ofst = ofst + 10
    ti = mfl(ti / 59049)
    mul = mul * 1024
  end
  local rem = n % 10
  for j = n + 1 - rem, n do
    local z = ti % 3
    if z == 0 then
      ecnt = ecnt + 1
      box[ecnt] = j
    elseif z == 1 then
      xv = xv + mul
    else
      yv = yv + mul
    end
    mul = mul * 2
    ti = mfl(ti / 3)
  end
  if 0 < ecnt then
    local ret = 0
    for j = 1, ecnt do
      local src = box[j]
      ret = ret + mmi(xlen[src][xv + 1], ylen[src][yv + 1])
    end
    rettbl[n - ecnt + 1] = mmi(rettbl[n - ecnt + 1], ret)
  end
end

print(table.concat(rettbl, "\n"))
-- print(os.clock())
