码风清奇请见谅

//7.21
//rng_58 bless me

#include<bits/stdc++.h>
using namespace std;
//fast io:
inline int Read() {
	int s = 0,f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') {
			f = -1;
		}
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline void Wte(int x) {
    if(x < 0) {
    	putchar('-');
		x = -x;
	}
    if(x > 9)  {
		Wte(x / 10);
	}
    putchar(x % 10 + '0');
}
inline void Write(int x) {
	Wte(x);
	putchar(' ');
}
//define:
#define REP(i,n) for(int i = 0; i < n; i++)
//const:
const int MAXN = 20;
//something:
int cost[MAXN][MAXN],v[MAXN];
int N,M;
vector <int> g[1010],path;
int ans = 1e9,sum,tot;
void iint() {
	REP(i,N) {
		REP(j,N) {
			cost[i][j] = INT_MAX;
		}
	}
}
int p;
bool cmp(int a,int b) {
	return cost[p][a] < cost[p][b];
}
void dfs(int a = 0,int b = 0) {
	if(path.size() == N) {
		ans = min(ans,sum);
		return;
	}
	for(int i = a;i < path.size();i++) {
		int x = path[i];
		if(sum + tot * v[x] >= ans) {
			return;
		}
		for(int j = b;j < g[x].size();j++) {
			int nx = g[x][j];
			if(!v[nx]) {
				path.push_back(nx);
				tot -= cost[nx][g[nx][0]]; sum += cost[x][nx] * v[x]; v[nx] = v[x] + 1;
				dfs(i,j + 1);
				tot += cost[nx][g[nx][0]]; sum -= cost[x][nx] * v[x]; v[nx] = 0; path.pop_back();
			}
		}
		b = 1;
	}
}
//run:
void solve() {
	N = Read(); M = Read();
	if(N == 1) {
		puts("0"); return;
	}
	iint();
	REP(i,M) {
		int x = Read() - 1,y = Read() - 1,z = Read();
		if(cost[x][y] == INT_MAX) {
			g[x].push_back(y); g[y].push_back(x);
		}
		cost[x][y] = min(cost[x][y],z); cost[y][x] = min(cost[y][x],z);
	}
	REP(i,N) {
		if(!g[i].empty()) {
			p = i;
			sort(g[i].begin(),g[i].end(),cmp);
			tot += cost[i][g[i][0]];
		}
	}
	/*REP(i,N) {
		cout << i << ':';
		REP(j,g[i].size()) {
			cout << ' ' << g[i][j];
		}
		cout << endl;
	}*/
	REP(i,N) {
		path.clear();
		path.push_back(i);
		tot -= cost[i][g[i][0]]; v[i] = 1;
		dfs();
		tot += cost[i][g[i][0]]; v[i] = 0;
	}
	cout << ans << endl;
}
//times:
void Times(int T) {
	while(T--) {
		solve();
	}
}
//begin:
int main() {
	int T;
	T = 1;
	//T = read();
	Times(T);
	return 0;
}