#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
//int beki[20];
int N, M;
ll paths[15][15];
ll csum = 0;
ll clique[1 << 15];
//int maxi[15000000];
//int convert[1 << 15];
//int path[1 << 15][15];
ll ans = 0;
ll dp[1 << 15][15];
l_l before[1<<15][15];
int main() {
    cin >> N >> M;
    /*
    beki[0] = 1;
    for(int i = 1; i <= 16; i++) {
        beki[i] = beki[i-1] * 3;
    }
    */
    /*
    for(int bits = 0; bits < (1 << N); bits++) {
        for(int i = 0; i < N; i++) {
            if(bits & (1 << i)) {
                convert[bits] += beki[i];
            }
        }
    }
    */
    for(int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        paths[a][b] = c;
        paths[b][a] = c;
        csum += c;
    }
    for(int bits = 0; bits < (1 << N); bits++) {
        for(int i = 0; i < N; i++) {
            if(!(bits & (1 << i))) continue;
            for(int j = 0; j < i; j++) {
                if(!(bits & (1 << j))) continue;
                clique[bits] += paths[i][j];
            }
        }
        /*
        for(int sub = (1 << N); ;) {
            sub = (sub - 1) & (~bits);
            if(sub == 0) break;
            int tmp = 0;
            for(int i = 0; i < N; i++) {
                if(bits & (1 << i)) tmp += convert[bits];
                if(sub & (1 << i)) tmp += 2 * convert[sub];
            }
            for(int i = 0; i < N; i++) {
                if(!(bits & (1 << i))) continue;
                for(int j = 0; j < N; j++) {
                    if(!(sub & (1 << j))) continue;
                    chmax(maxi[tmp], paths[i][j]);
                }
            }
            //cerr << bitset<15>(bits) << " " << bitset<15>(sub) << " " << maxi[tmp] << endl;
        }
        */
    }
    /*
    for(int i = 0; i < (1 << N); i++) {
        cerr << bitset<15>(i) << " " << clique[i] << endl;
    }
    */
    for(int bits = 0; bits < (1 << N); bits++) {
        //if(!(bits & 1)) continue;
        for(int i = 0; i < N; i++) {
            if(!(bits & (1 << i))) continue;
            dp[bits][i] = -1e9;
            if(i == 0) {
                dp[bits][i] = clique[bits];
                continue;
            }
            for(int sub = bits; ;) {
                sub = (sub - 1) & bits;
                if(sub == 0) break;
                if(!(sub & (1 << i))) continue;
                int from = bits & (~sub);
                for(int j = 0; j < N; j++) {
                    if(!(from & (1 << j))) continue;
                    if(paths[j][i] == 0) continue;
                    ll val = dp[from][j] + clique[sub] + paths[j][i];
                    //cerr << bits << " " << i << " " << sub << " " << j << " " << val << endl;
                    if(chmax(dp[bits][i], val)) {
                        before[bits][i] = {from, j};
                    }
                }
            }
            //cerr << bits << " " << i << " " << dp[bits][i] << endl;
            /*
            if(csum - dp[bits][i] < 133677) {
                cerr << bitset<15>(bits) << " " << i << endl;
                cerr << dp[bits][i] << " " << csum - dp[bits][i] << endl;
                assert(0);
            }
            */
        }
    }
    ll nowbits = 0;
    ll nowpos;
    for(int bits = 0; bits < (1 << N); bits++) {
        if(chmax(ans, dp[bits][N-1])) {
            nowbits = bits;
            nowpos = N - 1;
        }
    }
    /*
    while(true) {
        cerr << bitset<15>(nowbits) << " " << nowpos << endl;
        if(nowpos == 0) break;
        l_l tmp = before[nowbits][nowpos];
        nowbits = tmp.first;
        nowpos = tmp.second;
    }
    cerr << csum << " " << ans << endl;
    */
    cout << csum - ans << endl;
    return 0;
}

Measured memory_bytes: 12032