// 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 bs_max = (1 << n) - 1;
    let mut dp = vec![vec![None; n]; 1 << n];
    dp[1][0] = Some(0);
    for bs in (0..1 << n).filter(|&bs| bs & 1 == 1) {
        for x in (0..n).filter(|&x| bs >> x & 1 == 1) {
            if let Some(crr) = dp[bs][x] {
                for cs in std::iter::successors(Some(bs_max & !bs), |&cs| {
                    if cs == 0 {
                        None
                    } else {
                        Some((cs - 1) & !bs)
                    }
                }) {
                    dp[bs | cs][x].change_max(Some(crr + w[cs | 1 << x]));
                }

                for y in (0..n).filter(|&y| bs >> y & 1 == 0 && adj[x][y] != 0) {
                    dp[bs | 1 << y][y].change_max(Some(crr + adj[x][y]));
                }
            }
        }
    }

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


Measured memory_bytes: 7072