use std::collections::*;
use std::io::*;
use std::*;
// template {{{
macro_rules! get {
    ($($t:tt),*; $n:expr) => {
        {
            let stdin = std::io::stdin();
            let ret = std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
                let line = line.unwrap();
                let mut it = line.split_whitespace();
                _get!(it; $($t),*)
            }).collect::<Vec<_>>();
            ret
        }
    };
    ($($t:tt),*) => {
        {
            let mut line = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut it = line.split_whitespace();
            _get!(it; $($t),*)
        }
    };
}
macro_rules! _get {
    ($it:ident; [char]) => {
        _get!($it; String).chars().collect::<Vec<_>>()
    };
    ($it:ident; [u8]) => {
        _get!($it; String).bytes().collect::<Vec<_>>()
    };
    ($it:ident; usize1) => {
        $it.next().unwrap().parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
    };
    ($it:ident; [usize1]) => {
        $it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
    };
    ($it:ident; [$t:ty]) => {
        $it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
    };
    ($it:ident; $t:ty) => {
        $it.next().unwrap().parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
    };
    ($it:ident; $($t:tt),+) => {
        ($(_get!($it; $t)),*)
    };
}
// }}}

fn main() {
    let n = get!(usize);
    let vil = get!(i32,i32,i64;n);
    let mut ans = vec![1 << 60; n + 1];
    let horimin: Vec<Vec<_>> = (0..1 << n)
        .map(|i| {
            (0..n)
                .map(|j| {
                    iter::once(vil[j].1.abs())
                        .chain(
                            (0..n)
                                .filter(|x| i as i32 & (1 << x) != 0)
                                .map(|x| (vil[j].1 - vil[x].1).abs()),
                        )
                        .min()
                        .unwrap()
                })
                .collect()
        })
        .collect();
    let vertmin: Vec<Vec<_>> = (0..1 << n)
        .map(|i| {
            (0..n)
                .map(|j| {
                    iter::once(vil[j].0.abs())
                        .chain(
                            (0..n)
                                .filter(|x| i as i32 & (1 << x) != 0)
                                .map(|x| (vil[j].0 - vil[x].0).abs()),
                        )
                        .min()
                        .unwrap()
                })
                .collect()
        })
        .collect();
    for i in 0..(1 << n) {
        let overs: Vec<_> = (0..n).filter(|x| i as i32 & (1 << x) != 0).collect();
        for j in 0..(1 << overs.len()) {
            let mut hori = i;
            for k in 0..overs.len() {
                if j & (1 << k) != 0 {
                    hori &= !(1 << overs[k]);
                }
            }
            let vert = i & !hori;
            let s: i64 = (0..n)
                .map(|x| horimin[hori][x].min(vertmin[vert][x]) as i64 * vil[x].2)
                .sum();
            ans[overs.len()] = ans[overs.len()].min(s);
        }
    }
    ans.iter().map(|x| println!("{}", x)).count();
}


Measured memory_bytes: 8584