#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <numeric>
#include <bitset>
#include <ext/algorithm>
#include <ext/numeric>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
typedef long long LL; using namespace std;

int n, m;

const int MAXN = 20;

bool g[MAXN][MAXN];
int cost[MAXN][MAXN];

int dp[1 << 16][15][15];

const int INF = -2;

int memo(int mask, int s, int e) {
	if (s == e)
		return 0;
	if (s > e)
		return memo(mask, e, s);
	int &ret = dp[mask][s][e];
	if (ret != -1)
		return ret;
	ret = INF;
	vector<pair<int, int> > edges;
	vector<int> costs;
	int sum, bits = 1 << s, bite = 1 << e;
	int w, bitw, ret1, ret2;
	int tmp, v;
	vector<int> vertices;
	FOR (i, n)
		if (mask & (1 << i))
			vertices.pb(i);
  for(int a = mask; ; a = (a - 1) & mask) {
  	if(a == 0)
			break;
		if (!(a & bits))
			continue;
		if (a & bite)
			continue;
		edges.clear();
		costs.clear();
		sum = 0;
		FOR (i, vertices.sz) {
			v = vertices[i];
			if (a & (1 << v)) {
				FOR (j, vertices.sz) {
					w = vertices[j];
					if (!g[v][w])
						continue;
					bitw = 1 << w;
					if ((mask & bitw) && !(a & bitw)) {
			edges.pb(make_pair(v, w));
						sum += cost[v][w];
						costs.pb(cost[v][w]);
					}
				}
			}
		}
		FOR (i, edges.sz) {
			ret1 = memo(a, s, edges[i].first);
			if (ret1 == INF || (ret != INF && ret1 + sum - costs[i] >= ret))
				continue;
	 		ret2 = memo(mask ^ a, edges[i].second, e);
			if (ret2 != INF) {
				tmp = ret1 + ret2 + sum - costs[i];
				if (ret == INF || tmp < ret)
					ret = tmp;
			}
		}
  }
	return ret;
}

int main() {
	SET(g, 0);
	scanf("%d %d", &n, &m);
	int x, y, c;
	FOR (i, m) {
		scanf("%d %d %d", &x, &y, &c);
		x--;
		y--;
		g[x][y] = g[y][x] = true;
		cost[x][y] = cost[y][x] = c;
	}
	SET(dp, 255);
	printf("%d\n", memo((1 << n) - 1, 0, n - 1));
	return 0;
}