output_description: Print the answer in N+1 lines.  
  The i-th line (i = 1, \ldots, N+1) should contain the minimum possible value
  of S after building railroads for the case K = i-1.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      X_1 Y_1 P_1
      X_2 Y_2 P_2
       :  :  :
      X_N Y_N P_N
attempt: import itertools
  
  G = []
  MAX = 10**9 + 1
  
  
  def calcS(R_x, R_y):
      S = 0
      for g in G:
          near_r = MAX
          x, y, p = g
          for r in R_x:
              if near_r == 0:
                  break
              near_r = min(near_r, abs(x - r))
          for r in R_y:
              if near_r == 0:
                  break
              near_r = min(near_r, abs(y - r))
          S += p * near_r
      return S
  
  
  def resolve():
      global G
  
      n = int(input())
      G = []
  
      # 道路の建設予定地
      pre_x = set()
      pre_y = set()
      # pre[i] = [x or y, index]
      pre = []
  
      for _ in range(n):
          x, y, p = list(map(int, input().split()))
          if x not in pre_x:
              pre_x.add(x)
              pre.append(["x", x])
          if y not in pre_y:
              pre_y.add(y)
              pre.append(["y", y])
          G.append([x, y, p])
  
      for i in range(n + 1):
          if i == 0:
              print(calcS([0], [0]))
              continue
  
          min_S = MAX
          # i本通路を建設する
          for R in itertools.combinations(pre, i):
              R_x = [0]
              R_y = [0]
              for r in R:
                  if r[0] == "x":
                      R_x.append(r[1])
                  else:
                      R_y.append(r[1])
              min_S = min(min_S, calcS(R_x, R_y))
  
          print(min_S)
  
  
  resolve()
  
problem_description: Statement
  
  New AtCoder City has an infinite grid of streets, as follows:
  
    * At the center of the city stands a clock tower. Let (0, 0) be the coordinates of this point.
    * A straight street, which we will call _East-West Main Street_ , runs east-west and passes the clock tower. It corresponds to the x-axis in the two-dimensional coordinate plane.
    * There are also other infinitely many streets parallel to East-West Main Street, with a distance of 1 between them. They correspond to the lines \ldots, y = -2, y = -1, y = 1, y = 2, \ldots in the two-dimensional coordinate plane.
    * A straight street, which we will call _North-South Main Street_ , runs north-south and passes the clock tower. It corresponds to the y-axis in the two-dimensional coordinate plane.
    * There are also other infinitely many streets parallel to North-South Main Street, with a distance of 1 between them. They correspond to the lines \ldots, x = -2, x = -1, x = 1, x = 2, \ldots in the two-dimensional coordinate plane.
  
  There are N residential areas in New AtCoder City. The i-th area is located at
  the intersection with the coordinates (X_i, Y_i) and has a population of P_i.
  Each citizen in the city lives in one of these areas.
  
  **The city currently has only two railroads, stretching infinitely, one along
  East-West Main Street and the other along North-South Main Street.**  
  M-kun, the mayor, thinks that they are not enough for the commuters, so he
  decides to choose K streets and build a railroad stretching infinitely along
  each of those streets.
  
  Let the _walking distance_ of each citizen be the distance from his/her
  residential area to the nearest railroad.  
  M-kun wants to build railroads so that the sum of the walking distances of all
  citizens, S, is minimized.
  
  For each K = 0, 1, 2, \dots, N, what is the minimum possible value of S after
  building railroads?
samples: [{"input": "3\n    1 2 300\n    3 3 600\n    1 4 800", "output": "2900\n    900\n    0\n    0\n    \n\nWhen K = 0, the residents of Area 1, 2, and 3 have to walk the distances of 1,\n3, and 1, respectively, to reach a railroad.  \nThus, the sum of the walking distances of all citizens, S, is 1 \\times 300 + 3\n\\times 600 + 1 \\times 800 = 2900.\n\nWhen K = 1, if we build a railroad along the street corresponding to the line\ny = 4 in the coordinate plane, the walking distances of the citizens of Area\n1, 2, and 3 become 1, 1, and 0, respectively.  \nThen, S = 1 \\times 300 + 1 \\times 600 + 0 \\times 800 = 900.  \nWe have many other options for where we build the railroad, but none of them\nmakes S less than 900.\n\nWhen K = 2, if we build a railroad along the street corresponding to the lines\nx = 1 and x = 3 in the coordinate plane, all citizens can reach a railroad\nwith the walking distance of 0, so S = 0. We can also have S = 0 when K = 3.\n\nThe figure below shows the optimal way to build railroads for the cases K = 0,\n1, 2.  \nThe street painted blue represents the roads along which we build railroads.\n\n![](https://img.atcoder.jp/m-solutions2020/fc274bed71a4c37706550fa083496d39.png)\n\n* * *"}, {"input": "5\n    3 5 400\n    5 3 700\n    5 5 1000\n    5 7 700\n    7 5 400", "output": "13800\n    1600\n    0\n    0\n    0\n    0\n    \n\nThe figure below shows the optimal way to build railroads for the cases K = 1,\n2.\n\n![](https://img.atcoder.jp/m-solutions2020/7c6b7a31998a1c46fba4c0679b023822.png)\n\n* * *"}, {"input": "6\n    2 5 1000\n    5 2 1100\n    5 5 1700\n    -2 -5 900\n    -5 -2 600\n    -5 -5 2200", "output": "26700\n    13900\n    3200\n    1200\n    0\n    0\n    0\n    \n\nThe figure below shows the optimal way to build railroads for the case K = 3.\n\n![](https://img.atcoder.jp/m-solutions2020/0453fa9c2f02c3bd5d5f9e20d0e8e589.png)\n\n* * *"}, {"input": "8\n    2 2 286017\n    3 1 262355\n    2 -2 213815\n    1 -3 224435\n    -2 -2 136860\n    -3 -1 239338\n    -2 2 217647\n    -1 3 141903", "output": "2576709\n    1569381\n    868031\n    605676\n    366338\n    141903\n    0\n    0\n    0\n    \n\nThe figure below shows the optimal way to build railroads for the case K = 4.\n\n![](https://img.atcoder.jp/m-solutions2020/464ce76d1d7d72638eb372342f8386c5.png)"}]