#include <iostream>
#include <cstring>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 14, SIZE2 = 1 << SIZE, INF = 0x3f3f3f3f3f3f3f3f;

int N, M;
int D[SIZE][SIZE], G[SIZE][SIZE2];
int F[SIZE][SIZE2];

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> N >> M;

	memset(D, 0x3f, sizeof D);
	for (int i = 0; i < N; i ++) D[i][i] = 0;

	while (M --)
	{
		int u, v, c;
		cin >> u >> v >> c;
		u --, v --;
		D[u][v] = D[v][u] = min(D[u][v], c);
	}

	memset(G, 0x3f, sizeof G);
	for (int i = 0; i < N; i ++)
		for (int j = 0; j < 1 << N; j ++)
			for (int k = 0; k < N; k ++)
				if (j >> k & 1)
					G[i][j] = min(G[i][j], D[i][k]);

	memset(F, 0x3f, sizeof F);
	for (int i = 0; i < N; i ++) F[0][1 << i] = 0;

	for (int i = 1; i < 1 << N; i ++)
		for (int j = i - 1 & i; j; j = j - 1 & i)
		{
			int Left = i ^ j, Cost = 0;
			for (int k = 0; k < N; k ++)
				if (j >> k & 1)
				{
					Cost += G[k][Left];
					if (Cost >= INF) break;
				}
			if (Cost >= INF) continue;
			for (int k = 1; k < N; k ++)
				F[k][i] = min(F[k][i], F[k - 1][Left] + Cost * k);
		}

	int Result = INF;
	for (int i = 0; i < N; i ++)
		Result = min(Result, F[i][(1 << N) - 1]);

	cout << Result << endl;

	return 0;
}