// ordtools {{{
#[allow(dead_code)]
mod ordtools {
    pub trait Ordtools: PartialOrd + Sized {
        fn change_min(&mut self, mut rhs: Self) {
            if self > &mut rhs {
                *self = rhs;
            }
        }

        fn change_max(&mut self, mut rhs: Self) {
            if self < &mut rhs {
                *self = rhs;
            }
        }
    }

    impl<T: PartialOrd + Sized> Ordtools for T {}
}
// }}}
// dbg {{{
#[allow(dead_code)]
mod dbg {
    use std::fmt::{Debug, Formatter};

    #[derive(Clone)]
    pub struct Tabular<'a, T: Debug>(pub &'a [Vec<T>]);
    impl<'a, T: Debug> Debug for Tabular<'a, T> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            for i in 0..self.0.len() {
                writeln!(f, "{:2} | {:?}", i, &self.0[i])?;
            }
            Ok(())
        }
    }

    #[derive(Clone)]
    pub struct BooleanTable<'a>(pub &'a [Vec<bool>]);
    impl<'a> Debug for BooleanTable<'a> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            for i in 0..self.0.len() {
                writeln!(f, "{:2} | {:?}", i, BooleanSlice(&self.0[i]))?;
            }
            Ok(())
        }
    }

    #[derive(Clone)]
    pub struct BooleanSlice<'a>(pub &'a [bool]);
    impl<'a> Debug for BooleanSlice<'a> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            write!(
                f,
                "{}",
                self.0
                    .iter()
                    .map(|&b| if b { '#' } else { '.' })
                    .collect::<String>()
            )?;
            Ok(())
        }
    }
}
// }}}

use ordtools::Ordtools;
use proconio::{input, marker::Usize1};

fn main() {
    input!(n: usize, m: usize, abc: [(Usize1, Usize1, u32); m]);

    let all = abc.iter().map(|&(_, _, c)| c).sum::<u32>();

    let mut adj = vec![vec![0; n]; n];
    (0..n).for_each(|i| adj[i][i] = 0);
    for (a, b, c) in abc {
        adj[a][b] = c;
        adj[b][a] = c;
    }

    let mut w = vec![0; 1 << n];
    for mask in 0..1 << n {
        for i in (0..n).filter(|&i| mask >> i & 1 == 1) {
            for j in (i + 1..n).filter(|&j| mask >> j & 1 == 1) {
                w[mask] += adj[i][j];
            }
        }
    }

    let mut dp = vec![vec![0; n]; 1 << n];
    for bs in 1..1 << n {
        for cs in std::iter::successors(Some((1 << n) & !bs), |aug| {
            let cs = (aug - 1) & !bs;
            if cs == 0 {
                None
            } else {
                Some(cs)
            }
        }) {
            for x in (0..n).filter(|&x| bs >> x & 1 == 1) {
                for y in (0..n).filter(|&y| cs >> y & 1 == 1 && adj[x][y] != 0) {
                    let z = dp[bs][x] + w[cs] + adj[x][y];
                    dp[bs | cs][y].change_max(z);
                }
            }
        }
    }

    let max_span = (0..1 << n).map(|bs| dp[bs][n - 1]).max().unwrap();
    println!("{}", all - max_span);
}
