#include <cstdio>

int n, m, x[20], min = 1<<30, v[20], d[20], sol[20];
struct nod
{
	int x, cost;
	nod *next;
};
nod *G[20];

void addMuchie(int i, int j, int cost)
{
	nod *p = new nod;
	p->x = j;
	p->cost = cost;
	p->next = G[i];
	G[i] = p;
}

void back(int k, int cost)
{
	if (k == n + 1 && (cost + d[x[k-1]] < min) && d[x[k-1]] != 0)
	{
		min = cost + d[x[k-1]];
//		for (int i = 1; i <= n; ++i)	sol[i] = x[i];
		return;
	}
	
	for (nod *p = G[x[k-1]]; p; p = p->next)
		if (!v[p->x])
		{
			x[k] = p->x;
			v[p->x] = 1;
			back(k+1, cost + (p->cost));
			v[p->x] = 0;
		}
	
}

int main()
{
	FILE *f = fopen("hamilton.in", "r");
	fscanf(f, "%d%d", &n, &m);
	for (int i, y, c;m;--m)
	{
		fscanf(f, "%d%d%d", &i, &y, &c);
		++i, ++y;
		addMuchie(i, y, c);
		if (i == 1)
			d[y] = c;
	}
	fclose(f);
	x[1] = 1;
	v[1] = 1;
	back(2, 0);
	f = fopen("hamilton.out", "w");
	fprintf(f, "%d\n", min);
//	for (int i = 1; i <= n ; ++i)	fprintf(f, "%d ", sol[i]);
//	fprintf(f, "1\n");
	fclose(f);
	
	return 0;
}