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: N = int(input())
  L = []
  X = {}
  Y = {}
  
  LX = [0]
  LY = [0]
  for i in range(N):
      x, y, p = map(int, input().split())
      L.append([x, y, p])
      if x not in X:
          X[x] = p
      else:
          X[x] += p
      if y not in Y:
          Y[y] = p
      else:
          Y[y] += p
  
  # print(X,Y)
  
  ans = []
  cnt = 0
  for i in range(N):
      cnt += min(abs(L[i][0]), abs(L[i][1])) * L[i][2]
  ans.append(cnt)
  # print(ans)
  for i in range(N):
      Xmax = 0
      Xkey = 0
      for k, v in X.items():
          if Xmax < v:
              Xmax = v
              Xkey = k
      Ymax = 0
      Ykey = 0
      for k, v in Y.items():
          if Ymax < v:
              Ymax = v
              Ykey = k
      if Xmax > Ymax:
          LX.append(Xkey)
          for q in range(N):
              if L[q][0] == Xkey:
                  L[q] = [0, 0, 0]
  
      else:
          LY.append(Ykey)
          for q in range(N):
              if L[q][1] == Ykey:
                  L[q] = [0, 0, 0]
      X = {}
      Y = {}
      for q in range(N):
          if L[q][0] not in X:
              X[L[q][0]] = L[q][2]
          else:
              X[L[q][0]] += L[q][2]
          if L[q][1] not in Y:
              Y[L[q][1]] = L[q][2]
          else:
              Y[L[q][1]] += L[q][2]
      cnt = 0
      for l in range(N):
          mlen = 10**20
          for x in range(len(LX)):
              if mlen > abs(LX[x] - L[l][0]):
                  mlen = abs(LX[x] - L[l][0])
          for y in range(len(LY)):
              if mlen > abs(LY[y] - L[l][1]):
                  mlen = abs(LY[y] - L[l][1])
          cnt += mlen * L[l][2]
      ans.append(cnt)
  
  for i in ans:
      print(i)
  
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)"}]