fileprivate struct Scanner {
    private var elements = [String]()
    private var index = 0
    
    mutating func peek() -> String {
        while elements.count == index {
            elements = readLine()!.split(separator: " ").map(String.init)
            index = 0
        }
        return elements[index]
    }
    
    mutating func next() -> String {
        let value = peek()
        index += 1
        return value
    }
    
    mutating func nextInt() -> Int {
        return Int(next())!
    }
    
    mutating func nextDouble() -> Double {
        return Double(next())!
    }
}

fileprivate struct Array2D<Element> {
    let n1: Int
    let n2: Int
    private var elements: [Element]
    
    init(repeating: Element, _ n1: Int, _ n2: Int) {
        self.n1 = n1
        self.n2 = n2
        self.elements = [Element](repeating: repeating, count: n1 * n2)
    }
    
    subscript(i: Int, j: Int) -> Element {
        get {
            elements[i * n2 + j]
        }
        set {
            elements[i * n2 + j] = newValue
        }
    }
}


func main() {
    var scanner = Scanner()
    let N = scanner.nextInt()
    var X = [Int]()
    var Y = [Int]()
    var P = [Int]()
    
    for _ in 0 ..< N {
        X.append(scanner.nextInt())
        Y.append(scanner.nextInt())
        P.append(scanner.nextInt() * 2)
    }
    
    func optimal(_ xs: [(Int, Int)]) -> Int {
        var now = 0
        var total = 0
        for i in xs.indices {
            total += xs[i].1
        }
        for i in xs.indices {
            now += xs[i].1
            if now >= total / 2 {
                var result = 0
                for j in xs.indices {
                    result += abs(xs[i].0 - xs[j].0) * xs[j].1
                }
                return result
            }
        }
        return 0
    }
    
    var answer = [Int](repeating: Int.max, count: N + 1)
    
    for k in 0 ..< (1 << N) {
        var xs = [(Int, Int)]()
        var ys = [(Int, Int)]()
        for i in 0 ..< N {
            if (k & 1 << i) != 0 {
                xs.append((X[i], P[i]))
            } else {
                ys.append((Y[i], P[i]))
            }
        }
        xs.sort { $0.0 < $1.0 }
        ys.sort { $0.0 < $1.0 }
        func solve(_ xs: [(Int, Int)]) -> Array2D<Int> {
            var dp = Array2D(repeating: Int.max, xs.count + 1, N + 1)
            dp[0, 0] = 0
            for i in 0 ..< xs.count {
                for j in 0 ... N where dp[i, j] != Int.max {
                    dp[i + 1, j] = min(dp[i + 1, j], dp[i, j] + abs(xs[i].0) * xs[i].1)
                }
                for k in i + 1 ... xs.count {
                    let cost = optimal(Array(xs[i ..< k]))
                    for j in 0 ..< N where dp[i, j] != Int.max {
                        dp[k, j + 1] = min(dp[k, j + 1], dp[i, j] + cost)
                    }
                }
            }
            return dp
        }
        let dpX = solve(xs)
        let dpY = solve(ys)
        for i in 0 ... N where dpX[xs.count, i] != Int.max {
            for j in 0 ... N where dpY[ys.count, j] != Int.max && i + j <= N {
                answer[i + j] = min(answer[i + j], dpX[xs.count, i] + dpY[ys.count, j])
            }
        }
    }
    
    for i in 0 ... N {
        print(answer[i] / 2)
    }
}

main()


Measured memory_bytes: 8080