/*
Cerberus97
Hanit Banga
*/

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include "unordered_map"
#include "bitset"

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false)

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

const int N = 15, S = (1 << N) + 10, inf = 1e9;

int dp[S][N], g[N][N] = {0}, n;
bool seen[S][N] = {0};
unordered_map <int, int> mp;

inline int cost(int s1, int s2);
int f(int i, int t);

int main()
{
	int m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int u, v, c;
		cin >> u >> v >> c;
		g[u - 1][v - 1] = g[v - 1][u - 1] = c;
	}

	int subsets = (1 << n);
	// for (int i = 1; i < subsets; ++i)
	// {
	// 	int temp = (1 << __builtin_popcount(i));
	// 	for (int j = 0; j < temp; ++j)
	// 	{
	// 		int s1 = 0, ctr = 0, u = -1;
	// 		for (int k = 0; k < n; ++k)
	// 		{
	// 			if (i & (1 << k))
	// 			{
	// 				if (j & (1 << ctr++))
	// 					s1 |= (1 << k);

	// 				else
	// 					u = k;
	// 			}
	// 		}

	// 		int s2 = i - s1, ans = 0;
	// 		if (s1 > s2)
	// 			continue;

	// 		for (int k = 0; k < n; ++k)
	// 			if (s1 & (1 << k))
	// 				ans += g[k][u];

	// 		ans += cost(s1, s2 - (1 << u));
	// 		mp[(s1 << N) + s2] = ans;
	// 	}
	// }

	// for (int i = 0; i < subsets; ++i)
	// {
	// 	for (int t = 0; t < n; ++t)
	// 	{
	// 		if (!(i & 1) or !(i & (1 << t)))
	// 		{
	// 			dp[i][t] = inf;
	// 			continue;
	// 		}

	// 		if (i == (1 << t))
	// 			continue;

	// 		dp[i][t] = inf;
	// 		int temp = (1 << __builtin_popcount(i));
	// 		for (int j = 1; j < temp - 1; ++j)
	// 		{
	// 			int s1 = 0, ctr = 0;
	// 			for (int k = 0; k < n; ++k)
	// 			{
	// 				if (i & (1 << k))
	// 				{
	// 					if (j & (1 << ctr++))
	// 						s1 |= (1 << k);
	// 				}
	// 			}

	// 			if ((s1 & 1) and (s1 & (1 << t)))
	// 				dp[i][t] = min(dp[i][t], dp[s1][t] + cost(s1 - (1 << t), i - s1));
	// 		}

	// 		if (t)
	// 		{
	// 			for (int u = 0; u < n; ++u)
	// 			{
	// 				if (u == t or !(i & (1 << u)) or !g[u][t])
	// 					continue;

	// 				dp[i][t] = min(dp[i][t], dp[i - (1 << t)][u] + cost(i - (1 << u), (1 << t)));
	// 			}
	// 		}
	// 	}
	// }

	cout << f(subsets - 1, n - 1);
	// cout << dp[subsets - 1][n - 1];
}

inline int cost(int s1, int s2)
{
	if (!s1 and !s2)
		return 0;
	
	s1 &= (~s2);
	if (s1 > s2)
		swap(s1, s2);
	
	int hash = (s1 << N) + s2;
	if (mp.find(hash) != mp.end())
		return mp[hash];

	int u = -1;
	for (u = 0; u < n and !(s2 & (1 << u)); ++u);

	int ans = cost(s1, s2 - (1 << u));
	for (int i = 0; i < n; ++i)
		if (s1 & (1 << i))
			ans += g[i][u];

	mp[hash] = ans;
	return ans;
}

int f(int i, int t)
{
	if (i == (1 << t))
		return 0;

	if (seen[i][t])
		return dp[i][t];

	seen[i][t] = true;
	int temp = (1 << __builtin_popcount(i)), ans = inf;
	for (int j = 1; j < temp - 1; ++j)
	{
		int s1 = 0, ctr = 0;
		for (int k = 0; k < n; ++k)
		{
			if (i & (1 << k))
			{
				if (j & (1 << ctr++))
					s1 |= (1 << k);
			}
		}

		if ((s1 & 1) and (s1 & (1 << t)))
			ans = min(ans, f(s1, t) + cost(s1 - (1 << t), i - s1));
	}

	if (t)
	{
		for (int u = 0; u < n; ++u)
		{
			if (u == t or !(i & (1 << u)) or !g[u][t])
				continue;

			ans = min(ans, f(i - (1 << t), u) + cost(i - (1 << u), (1 << t)));
		}
	}

	dp[i][t] = ans;
	return ans;
}

Measured memory_bytes: 120400