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: from itertools import product
  
  n = 15
  
  x = []
  y = []
  p = []
  for i in range(1, n + 1):
      x.append(i + 10000)
      y.append(i + 10000)
      p.append(i)
  
  yokomi = [0] * (1 << n)
  tatemi = [0] * (1 << n)
  
  
  for i in range(1 << n):
      yoko = [10000]
      tate = [10000]
      for j in range(n):
          if (i >> j) & 1 == 1:
              yoko.append(y[j])
              tate.append(x[j])
      for j in range(n):
          pp = 10**9
          qq = 10**9
          for e in yoko:
              if pp > abs(e - y[j]):
                  pp = abs(e - y[j])
          for e in tate:
              if qq > abs(e - x[j]):
                  qq = min(qq, abs(e - x[j]))
          yokomi[i] += pp * p[j]
          tatemi[i] += qq * p[j]
  
  
  def iter_p_adic(p, n):
      tmp = [range(p)] * n
      return product(*tmp)
  
  
  res = [10**20] * (n + 1)
  
  
  iterator = iter_p_adic(3, n)
  for idxs in iterator:
      c = 0
      xn = 0
      yn = 0
  
      for i in range(n):
          if idxs[i] == 1:
              yn += 1 << i
              c += 1
          elif idxs[i] == 2:
              xn += 1 << i
              c += 1
  
      tmp = 0
      tmp += min(tatemi[xn], yokomi[yn])
      if c < n + 1 and res[c] > tmp:
          res[c] = tmp
  for e in res:
      print(e)
  
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)"}]