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 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")
  flag[i] = false
end

local function findright(idxes, ofst)
  for i = ofst, #idxes do
    if flag[idxes[i]] then
      return i
    end
  end
  return false
end

local function getmincost(t, linecnt)
  local pos, val, idx = {}, {}, {}
  for k, v in pairs(t) do
    table.insert(pos, k)
    table.insert(val, v)
  end
  if #pos <= linecnt then
    return 0
  end
  for i = 1, #pos do idx[i] = i end
  table.sort(idx, function(a, b) return val[a] > val[b] end)
  for i = 1, linecnt do
    flag[idx[i]] = true
  end
  for i = linecnt + 1, #pos do
    flag[idx[i]] = false
  end
  local retval = 0
  table.sort(idx, function(a, b) return pos[a] < pos[b] end)
  local leftpos = false
  local rightpos = findright(idx, 1)
  for i = 1, #idx do
    local idx_i = idx[i]
    if flag[idx_i] then
      leftpos = rightpos
      if rightpos then
        rightpos = findright(idx, rightpos + 1)
      end
    else
      local cand = mab(pos[idx_i])
      if leftpos then
        cand = mmi(cand, mab(pos[idx_i] - pos[idx[leftpos]]))
      end
      if rightpos then
        cand = mmi(cand, mab(pos[idx_i] - pos[idx[rightpos]]))
      end
      retval = retval + cand * val[idx_i]
    end
  end
  return retval
end

for ik = 0, n do
  local tot = bls(1, n)
  local box = {}
  local ret = 0
  for i = 0, tot - 1 do
    local xs, ys = {}, {}
    local ti = i
    for j = 1, n do
      box[j] = ti % 2 == 0
      if ti % 2 == 0 then
        if not xs[x[j]] then
          xs[x[j]] = p[j]
        else
          xs[x[j]] = xs[x[j]] + p[j]
        end
      else
        if not ys[y[j]] then
          ys[y[j]] = p[j]
        else
          ys[y[j]] = ys[y[j]] + p[j]
        end
      end
      ti = brs(ti, 1)
    end
    local cand = 0
    for xline = 0, ik do
      local yline = ik - xline
      local xcost = getmincost(xs, xline)
      local ycost = getmincost(ys, yline)
      local z = xcost + ycost
      if xline == 0 then
        cand = z
      elseif z < cand then
        cand = z
      end
    end
    if i == 0 then
      ret = cand
    elseif cand < ret then
      ret = cand
    end
  end
  print(ret)
end
