#include <cstdio>
using namespace std;

int perm[20];
bool ap[20];
int costMuchie[20][20];
int N, M, SOL;

void back_ciclu(int pozitie, int costPartial)
{
	if (pozitie == N + 1) { /// s-a generat o permutare
		if (costMuchie[perm[N]][1] != 0) { /// exista muchia care inchide back_ciclul
			costPartial += costMuchie[perm[N]][1]; /// costul muchiei se adauga
			if (SOL > costPartial) {
				SOL = costPartial;
			}
		}
	} else {
		for (int i = 2; i <= N; ++i) {
			if (costMuchie[perm[pozitie - 1]][i] != 0) {/// exista muchie
				if (!ap[i]) {
					ap[i] = true;
					perm[pozitie] = i;
					back_ciclu(pozitie + 1, costPartial + costMuchie[perm[pozitie - 1]][i]);
					ap[i] = false;
				}
			}
		}
	}
}

int main()
{
	int a, b, c;

    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out","w", stdout);

	/// citirea datelor
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		++a;
		++b;
		costMuchie[a][b] = c;
	}

	/// calcularea solutiei
	SOL = 0x7fffffff; /// "+infinit" pe int
	perm[1] = 1;
	ap[1] = true;
	back_ciclu(2, 0);

	/// afisarea solutiei
	printf("%d\n", SOL);
	return 0;
}