use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
struct SubsetGenerator {
    subset: usize,
    set: usize,
}
#[allow(dead_code)]
impl SubsetGenerator {
    fn new(set: usize) -> SubsetGenerator {
        SubsetGenerator {
            subset: set & (-(set as i64) as usize),
            set: set,
        }
    }
}
impl Iterator for SubsetGenerator {
    type Item = usize;

    fn next(&mut self) -> Option<usize> {
        if self.subset == 0 {
            return None;
        }
        let ret = self.subset;
        self.subset = (self.subset as i64 - self.set as i64) as usize & self.set;
        Some(ret)
    }
}

#[test]
fn test_next_subset() {
    for s in SubsetGenerator::new(0b1101) {
        println!("{:04b}", s);
    }
    let mut iterator = SubsetGenerator::new(0b1101);
    assert!(iterator.next().unwrap() == 0b0001);
    assert!(iterator.next().unwrap() == 0b0100);
    assert!(iterator.next().unwrap() == 0b0101);
    assert!(iterator.next().unwrap() == 0b1000);
    assert!(iterator.next().unwrap() == 0b1001);
    assert!(iterator.next().unwrap() == 0b1100);
    assert!(iterator.next().unwrap() == 0b1101);
    assert!(iterator.next() == None);
}

struct Solver {
    matrix: Vec<Vec<i32>>,
    memo: Vec<Vec<i32>>,
    border: Vec<i32>,
}

impl Solver {
    fn new() -> Solver {
        let n = read::<usize>();
        let m = read::<usize>();
        let mut matrix = vec![vec![-1; n]; n];
        for _ in 0..m {
            let a = read::<usize>() - 1;
            let b = read::<usize>() - 1;
            let c = read::<i32>();
            matrix[a][b] = c;
            matrix[b][a] = c;
        }
        let mut border = vec![0; 1 << n];
        for group in 0..1 << n {
            let mut sum = 0;
            for i in 0..n {
                for j in i + 1..n {
                    if ((group >> i) & 1) == ((group >> j) & 1) {
                        continue;
                    }
                    if matrix[i][j] == -1 {
                        continue;
                    }
                    sum += matrix[i][j];
                }
            }
            border[group] = sum;
        }
        Solver {
            matrix: matrix,
            memo: vec![vec![-1; 1 << n]; n],
            border: border,
        }
    }
    fn calc(&mut self, from: usize, rest: usize) -> i32 {
        let n = self.matrix.len();
        if from == n - 1 {
            return self.border[rest | (1 << from)];
        }
        if self.memo[from][rest] != -1 {
            return self.memo[from][rest];
        }
        let mut ret = 1 << 30;
        for to in 0..n {
            if self.matrix[from][to] == -1 || ((rest >> to) & 1) == 0 {
                continue;
            }
            for group in SubsetGenerator::new(rest ^ (1 << to)).chain(0..1) {
                let nrest = rest ^ (1 << to) ^ group;
                let mut nret = self.border[group | (1 << from)];
                nret -= self.matrix[from][to] * 2;
                nret += self.calc(to, nrest);
                ret = std::cmp::min(ret, nret);
            }
        }
        self.memo[from][rest] = ret;
        ret
    }
    fn solve(&mut self) {
        let n = self.matrix.len();
        let rest = ((1 << n) - 1) ^ 1;
        let ans = self.calc(0, rest) / 2;
        println!("{}", ans);
    }
}

fn main() {
    let mut solver = Solver::new();
    solver.solve();
}

#[test]
fn max_case() {
    let mut solver = Solver {
        matrix: vec![vec![1; 15]; 15],
        memo: vec![vec![-1; 1 << 15]; 15],
        border: vec![1; 1 << 15],
    };
    solver.solve();
}


Measured memory_bytes: 6396