Scanf.scanf "%d" (fun n ->
    let xyp = Array.init n (fun _ -> Scanf.scanf " %d %d %d" (fun x y p -> x, y, p)) in

    let hp = Array.init (1 lsl n) (fun bit ->
        let rec loop j acc =
            if j = n then acc else
                if bit land (1 lsl j) = 0 then loop (j + 1) acc else
                    let _, k, _ = xyp.(j) in
                    loop (j + 1) (k :: acc)
        in
        let l = loop 0 [] in
        Array.init n (fun i ->
            let _, me, p = xyp.(i) in
            let rec loop acc = function
                | [] -> acc * p
                | k :: tl -> loop (min acc (abs (k - me))) tl
            in
            loop (abs me) l
        )
    )
    in
    let vp = Array.init (1 lsl n) (fun bit ->
        let rec loop j acc =
            if j = n then acc else
                if bit land (1 lsl j) = 0 then loop (j + 1) acc else
                    let k, _, _ = xyp.(j) in
                    loop (j + 1) (k :: acc)
        in
        let l = loop 0 [] in
        Array.init n (fun i ->
            let me, _, p = xyp.(i) in
            let rec loop acc = function
                | [] -> acc * p
                | k :: tl -> loop (min acc (abs (k - me))) tl
            in
            loop (abs me) l
        )
    )
    in
    let calc h v =
        let rec loop i acc =
            if i = n then acc else
                loop (i + 1) (acc + min v.(i) h.(i))
        in
        loop 0 0
    in

    let best = Array.make (n + 1) max_int in
    best.(0) <- calc hp.(0) vp.(0);
    let rec loop i c hbit vbit =
        if i < n then (
            loop (i + 1) c       hbit          vbit;

            let li = 1 lsl i in
            let q = min (calc hp.(hbit lor li) vp.(vbit)) (calc hp.(hbit) vp.(vbit lor li)) in
            best.(c + 1) <- min best.(c + 1) q;
            loop (i + 1) (c + 1) (hbit lor li) vbit;
            loop (i + 1) (c + 1) hbit          (vbit lor li);
        )
    in
    loop 0 0 0 0;

    Array.iter (Printf.printf "%d\n") best;
)