#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));
}

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

const int N = 16;
const int inf = 1e9;

int n, m;
int e[N][1 << N];
int c[N][N];
int dp[N][1 << N];

void minimize(int &x, int y) { x = (x > y) ? y : x; }

void prep() {
	for (int mask = 0; mask < (1 << n); ++mask) {
		for (int i = 0; i < n; ++i) if (!(mask >> i & 1)) {
			for (int j = 0; j < n; ++j) if (mask >> j & 1) e[i][mask] += c[i][j];
		}
	}
}

void brute(int pos, int cmask, int cost, int &u, int &mask) { 
// dp[u][mask] is the current state
// cmask is the next mask
	if (pos == n) {
		minimize(dp[u][cmask], dp[u][mask] + cost);
		return;
	}
	
	if (mask >> pos & 1) {
		return brute(pos + 1, cmask | (1 << pos), cost, u, mask);
	}

	brute(pos + 1, cmask, cost, u, mask);
	brute(pos + 1, cmask | (1 << pos), cost + e[pos][mask ^ (1 << u)], u, mask);
}

int main() {
	scanf("%d %d", &n, &m);
	while(m--) {
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		--u; --v;
		c[u][v] = c[v][u] = w;
	}

	prep();

	for (int mask = 0; mask < (1 << n); ++mask) {
		for (int i = 0; i < n; ++i) dp[i][mask] = inf;
	}

	dp[0][1] = 0;

	for (int mask = 0; mask < (1 << n); ++mask) {
		for (int u = 0; u < n; ++u) if (dp[u][mask] != inf) {
			
			for (int v = 0; v < n; ++v) if (!(mask >> v & 1)) {
				if (c[u][v] == 0) continue;
				minimize(dp[v][mask ^ (1 << v)], dp[u][mask] + e[v][mask ^ (1 << u)]);
			}

			brute(0, 0, 0, u, mask);
		}
	}

	printf("%d\n", dp[n - 1][(1 << n) - 1]);
}