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

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define IN(x,c) (find(c.begin(),c.end(),x) != (c).end())
#define REP(i,n) for (int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define INIT(a,v) memset(a,v,sizeof(a))
template<class A, class B> A cvt(B x) { stringstream ss; ss<<x; A y; ss>>y; return y; }

#define SPC << " " <<
#define DEBUG(x) cerr << #x << " = "; cerr << x << endl;
#define DEBUG_ITER(x) cerr << #x << " = "; for (auto _ : x) cerr << _ << ' '; cerr << endl;

typedef long long int64;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef array<int,3> III;

#define N 10
#define INF 1000000000

int n,m;
int a[N][N];

int mem[N][1<<N];
char done[N][1<<N];

int solve(int x, int v) {
	if (v==(1<<n)-1) {
		if (a[x][0]==0) return INF;
		else return a[x][0];
	}
	if (done[x][v]) return mem[x][v];
	int r=INF;
	REP (y,n) if (a[x][y]) {
		if (v&(1<<y)) continue;
		int ry = a[x][y]+solve(y, v|(1<<y));
		r=min(r, ry);
	}
	done[x][v]=1;
	mem[x][v]=r;
	return r;
}

int main() {
	freopen("test.in","r",stdin);
	cin >> n >> m;
	REP (i,m) {
		int x,y,z;
		cin >> x >> y >> z;
		a[x][y]=z;
		a[y][x]=z;
	}
	cout << solve(0,1) << endl;
	return 0;
}