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