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, idxes, linecnt, debug)
  if debug then print("---") end
  if #idxes <= linecnt then
    return 0
  end
  table.sort(idxes, function(a, b) return p[a] > p[b] end)
  local vv = {}
  local use = 0
  for i = 1, n do flag[i] = false end
  if 0 < linecnt then
    for i = 1, #idxes do
      local idxes_i = idxes[i]
      if not vv[t[idxes_i]] then
        use = use + 1
        flag[idxes_i] = true
        vv[t[idxes_i]] = true
      end
      if use == linecnt then break end
    end
  end
  -- for i = 1, linecnt do
  --   flag[idxes[i]] = true
  -- end
  -- for i = linecnt + 1, #idxes do
  --   flag[idxes[i]] = false
  -- end
  local retval = 0
  table.sort(idxes, function(a, b) return t[a] < t[b] end)
  local leftpos = false
  local rightpos = findright(idxes, 1)
  for i = 1, #idxes do
    local idxes_i = idxes[i]
    if flag[idxes_i] then
      leftpos = rightpos
      if rightpos then
        rightpos = findright(idxes, rightpos + 1)
      end
    else
      local cand = mab(t[idxes_i])
      if leftpos then
        cand = mmi(cand, mab(t[idxes_i] - t[idxes[leftpos]]))
      end
      if rightpos then
        cand = mmi(cand, mab(t[idxes_i] - t[idxes[rightpos]]))
      end
      if debug then print(i, cand, leftpos, rightpos, idxes_i, p[idxes_i]) end
      retval = retval + cand * p[idxes_i]
    end
  end
  if debug then print("sub" .. retval) 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
        table.insert(xs, j)
      else
        table.insert(ys, j)
      end
      ti = brs(ti, 1)
    end
    local cand = 0
    for xline = 0, ik do
      local yline = ik - xline
      local xcost = getmincost(x, xs, xline)
      local ycost = getmincost(y, ys, yline)
      local z = xcost + ycost
      do
        if ik == 4 and xline == 2 and table.concat(xs) == "6842" then
          -- getmincost(y, ys, yline, true)
          -- print(table.concat(xs) .. " " .. table.concat(ys), xcost, ycost)
        end
      end
      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
