/*
Enunt:
Se dau n orase identificate prin numerele 1,2,3,...,n. Se cunosc distantele intre m perechi de orase (i,j). Pe aceste drumuri se poate circula in ambele sensuri.
Ne intereseaza un traseu circular (excursie) care sa treaca prin fiecare oras cate o singura data si sa aiba lungimea totala cat mai mica.
De exemplu daca n=5, m=7 si cele m triplete (cele doua orase si distanta dintre ele ) sunt (1,2,1), (2,3,2), (3,4,6), (4,5,4), (5,1,7), (4,1,2),(3,5,1) atunci un posibil traseu de cost minim ar fi
1,2,3,5,4,1 cu suma distantelor 1+2+1+4+2=10
*/
/*
5 7
1 2 1
2 3 2
3 4 6
4 5 4
5 1 7
4 1 2
3 5 1
*/
#include <stdio.h>

FILE *in, *out;
int n, m, x[101], leg[101][101], vis[101], x_best[101], smin;

void backtrack(int k, int sum) {
	int i;

	if (k == n+1)
	{
		if (leg[x[n]][x[1]] > 0)
		{
			if (sum + leg[x[n]][x[1]] < smin)
			{
				smin = sum + leg[x[n]][x[1]];
				for (i=1; i<=n; i++)
				{
					x_best[i] = x[i];
				}
			}
		}
	}
	else
	{
		for (i=1; i<n; i++)
		{
			if ((vis[i] == 0) && (leg[x[k-1]][i] > 0))
			{
				x[k] = i;
				vis[i] = 1;
				backtrack(k+1, sum+leg[x[k-1]][i]);
				vis[i] = 0;
			}
		}
	}
}


int main ()
{
	int l1, l2, c, i, j;
	in = fopen("p48.in", "r");
	out = fopen("p48.out", "w");

	fscanf(in, "%d", &n);
	fscanf(in, "%d", &m);

	for (i=1; i<=m; i++)
	{
		fscanf(in, "%d", &l1);
		fscanf(in, "%d", &l2);
		fscanf(in, "%d", &c);
		leg[l1][l2] = c;
		// leg[l2][l1] = c;
	}

	smin = 2000000000;
	x[1] = 0;

	backtrack(2, 0);

	/*for (i=1; i<=n; i++)
	{
		fprintf(out, "%d ", x_best[i]);
	}*/

	if (smin == 2000000000)
		fprintf(out, "%s\n", "Nu exista solutie");
	else
		fprintf(out, "%d", smin);

	fclose(out);
	fclose(in);

	return 0;
}