#include <bits/stdc++.h>

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fm, to)    for (int i = fm; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 15, msksz = (1 << nsz) - 1, inf = 0x3f3f3f3f;
int n, m, full, lg[msksz + 5], g[nsz + 5], w[nsz + 5][nsz + 5], sum[msksz + 5], dp[msksz + 5][nsz + 5];

int inline at(int S, int id) { return S >> id & 1; }

int inline lowbit(int S) { return S & -S; }

string inline bin(int S, int len = n) {
	string s;
	loop (i, len) s += at(S, i) + 48;
	return s;
}

void inline upd(int &a, int b) { if (a < b) a = b; }

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> m;
	full = (1 << n) - 1;
	cont (i, m) {
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		g[u] |= 1 << v;
		g[v] |= 1 << u;
		::w[u][v] = ::w[v][u] = w;
	}
	loop (i, n) lg[1 << i] = i;
	
	memset(sum, -inf, sizeof(sum));
	sum[0] = 0;
	cont (S, full) {
		int u = lg[lowbit(S)];
		sum[S] = sum[S - lowbit(S)];
		for (int t = g[u] & S, d = t & -t; d; t -= d, d = t & -t) {
			int v = lg[d];
			sum[S] += w[u][v];
		}
	}
	memset(dp, -inf, sizeof(dp));
	cont (S, full) {
		if (!at(S, 0) || at(S, n - 1)) continue;
		dp[S][0] = sum[S];
	}
	circ (S, 0, full) {
		for (int rS = (S ^ full), T = rS; T; T = (T - 1) & rS) {
			if (sum[T] < 0) continue;
			for (int t = S, d = t & -t; d; t -= d, d = t & -t) {
				int u = lg[d];
				if (dp[S][u] < 0) continue;
				for (int t = T & g[u], d = t & -t; d; t -= d, d = t & -t) {
					int v = lg[d];
					upd(dp[S | T][v], dp[S][u] + sum[T] + w[u][v]);
				}
			}
		}
	}
	cout << sum[full] - dp[full][n - 1] << ln;
}
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;

const int N = 16;
const int M = (1 << N);
const int INF = 0x3f3f3f3f;

int dp[N][M], g[N][N], n, m, rv[M];

int f(int st, int msk){
    if(st == n - 1) return 0;
    if(dp[st][msk] != -1) return dp[st][msk];
    int sol = INF;
    for(int msk1 = (msk - 1) & msk; msk1 ; msk1 = (msk1 - 1) & msk){
        int msk2 = msk ^ msk1;
        if(msk1 & (1 << (n - 1))) continue;
        if(msk2 & (1 << st)) continue;
        int sum = 0;
        for(int t1 = msk1; t1 ; t1 -= t1 & (-t1)){
            for(int t2 = msk2 ; t2 ; t2 -= t2 & (-t2)){
                sum += g[rv[t1 & (-t1)]][rv[t2 & (-t2)]];
            }
        }
        for(int t2 = msk2 ; t2 ; t2 -= t2 & (-t2)){
            if(g[st][rv[t2 & (-t2)]]){
                sol = min(sol, f(rv[t2 & (-t2)], msk2) + sum - g[st][rv[t2 & (-t2)]]);
            }
        }

    }
    return dp[st][msk] = sol;
}

int main(){
    memset(dp, -1, sizeof(dp));
    for(int i = 0;i<N;i++) rv[(1 << i)] = i;
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &n, &m);
    for(int i = 0;i<m;i++){
        int x, y;scanf("%d%d", &x, &y);x--;y--;
        scanf("%d", &g[x][y]);
        g[y][x] = g[x][y];
    }
    printf("%d\n", f(0, (1 << n) - 1));
}
