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 calc list =
        Array.fold_left (fun acc (x, y, p) ->
            let dist = 
                List.fold_left (fun acc2 (flag, l) ->
                    if flag then min acc2 (abs (x - l)) 
                             else min acc2 (abs (y - l))) max_int list
            in
            acc + dist * p) 0 xyp
    in
    let init = [ true, 0; false, 0 ] in
    let best = Array.make (n + 1) max_int in
    best.(0) <- calc init;

    let rec loop i c l =
        if i < n then (
            loop (i + 1) c l;
            let x, y, p = xyp.(i) in
            let l1 = ((true, x) :: l) in
            let l2 = ((false, y) :: l) in
            let q1 = calc l1 in
            let q2 = calc l2 in
            best.(c + 1) <- min best.(c + 1) (min q1 q2);
            loop (i + 1) (c + 1) l1;
            loop (i + 1) (c + 1) l2;
        )
    in
    loop 0 0 init;

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