program ms_solution
  implicit none
  integer(8), parameter :: inf = 1e16
  integer :: n, i, j, k, l, u
  integer(8) :: x(15) = 0, y(15) = 0, p(15) = 0
  integer(8) :: mx(0:15, 15) = inf, my(0:15, 15) = inf, tx(15) = 0, ty(15) = 0
  integer(8) :: m
  read(*,*) n
  do i = 1, n
    read(*,*) x(i), y(i), p(i)
  end do
  u = lshift(1, n) - 1
  do i = 0, u
    k = popcnt(i)
    tx(1:n) = min(abs(x(1:n)), abs(y(1:n))) * p(1:n)
    ty(1:n) = tx(1:n)
    do j = 1, n
      if (.not.btest(i, j - 1)) cycle
      do l = 1, n
        tx(l) = min(tx(l), abs(x(l) - x(j)) * p(l))
        ty(l) = min(ty(l), abs(y(l) - y(j)) * p(l))
      end do
    end do
    if (sum(tx(1:n)) < sum(mx(k, 1:n))) mx(k, 1:n) = tx(1:n)
    if (sum(ty(1:n)) < sum(my(k, 1:n))) my(k, 1:n) = ty(1:n)
  end do
  do i = 0, n
    m = inf
    do j = 0, i
      m = min(m, sum(min(mx(j, 1:n), my(i - j, 1:n))))
    end do
    write(*,'(i0)') m
  end do
end program ms_solution