#include <bits/stdc++.h>
using namespace std;

int nth_bit(int64_t num, int n){
    return (num >> n) & 1;
}

int N, M;
int edges[15][15];
int gain[1<<15];

int dp[15][1<<15];
bool visited[15][1<<15];
const int INF = 1e9;

int rec(int start, int bits){
    if(bits == 0){
        return start == N-1 ? 0 : -INF;
    }
    if(visited[start][bits]) return dp[start][bits];

    int mx = -INF;
    for(int i=0; i<N; i++){
        if(nth_bit(bits, i) && edges[start][i]){
            mx = max(mx, rec(i, bits - (1<<i)) + edges[start][i]);
        }
    }

    for(int bits2=bits; bits2>0; bits2=(bits2-1)&bits){
        mx = max(mx, rec(start, bits - bits2) + gain[bits2 + (1<<start)]);
    }
    dp[start][bits] = mx;
    visited[start][bits] = true;
    return mx;
}

int main(){
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        edges[a][b] = c;
        edges[b][a] = c;
        for(int bits=0; bits<(1<<N); bits++){
            if(nth_bit(bits, a) && nth_bit(bits, b)) gain[bits] += c;
        }
    }
    cout << gain[(1<<N)-1] - rec(0, (1<<N)-2) << endl;
    return 0;
}