// Infoarena - Arhiva Educationala Ciclu Hamiltonian de Cost minim
// Februrie 2012 Marius Dumitran
// Dinamica pe submultimi. O(2^N * N^2)

#include<string.h>
#include<stdio.h>
#include<set>
#include<vector>

using namespace std;

int mat[19][19];
int sol[(1<<18)][19];

int main() {
	
	int N, M;
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	scanf("%d %d", &N, &M);
	
	memset(mat, 111, sizeof(mat));
	for (int i = 1; i <= M; ++i) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		mat[a][b] = c;
		
	}
	
	memset(sol, 11, sizeof(sol));
	sol[1][0] = 0;
	
	int toate = (1<<N) - 1;
	for( int i = 1; i <= toate; ++i) {
		for( int j = 0; j < N; ++j) {
			if( sol[i][j] > 20000000) continue;
			for( int k = 0; k < N; ++k) {
				if( ((1<<k) & i )) continue;
				int new_config = (i ^ (1<<k));
				if( sol[new_config][k] > sol[i][j] + mat[j][k] ){
					sol[new_config][k] = sol[i][j] + mat[j][k];
				}
			}
		}
		
	}
	int optim = 20000000;
	for( int i = 0; i < N; ++i) {
		if( sol[toate][i] + mat[i][0] < optim ) 
			optim = sol[toate][i] + mat[i][0];
		
	}
	printf("%d\n", optim);
	
	return 0;
}