#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 19
#define INF 0xFFFFFFF

int N, M, Cost[MAX][MAX], Best[MAX][(1<<18)+1], Source[MAX][(1<<18)+1];

int main() {
	int X, Y, Z;

	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d %d %d", &X, &Y, &Z);
		Cost[X][Y] = Z;
	}
	
	for (int i = 0; i < N; i++) 
	for (int j = 0; j < (1 << N); j++){
		Best[i][j] = INF;
	}

	for (int i = 0; i < N; i++) {
		Best[i][1<<i] = 0;
		Source[i][1<<i] = i;
	}

	for (int j = 0; j < (1 << N); j++) 
	for (int i = 0; i < N; i++) 
		if (j & (1 << i)) {
			for (int k = 0; k < N; k++)
				if (((j ^ (1 << i)) & (1 << k)) && Cost[k][i] > 0) {
					if (Best[i][j] > Best[k][j ^ (1 << i)] + Cost[k][i]) {
						Best[i][j] = Best[k][j ^ (1 << i)] + Cost[k][i];
						Source[i][j] = Source[k][j ^ (1 << i)];
					}
				}	
		}
	
	int Sol = INF;
	for (int i = 0; i < N; i++) 
	if (i != Source[i][(1<<N)-1] && Cost[i][Source[i][(1<<N)-1]] > 0) {
		Sol = min(Sol, Best[i][(1<<N)-1] + Cost[i][Source[i][(1<<N)-1]]);
	}
	
	printf("%d\n", Sol);
	
	return 0;
}