#include <stdio.h>
#include <stdlib.h>
#define MAXN 18
#define INF 18000001
#define MAXP 262145
int mat[MAXN][MAXN], d[MAXP][MAXN], vec[MAXN][MAXN], v[MAXN];

inline int minim(int a, int b){
	return a<b?a:b;
}

int main()
{
    FILE *fin, *fout;
    int n, m, i, x, y, p, k, j;
    fin=fopen("hamilton.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(i=0; i<n; i++)
			for(j=0; j<n; j++)
				mat[i][j]=INF;
		p=1<<n;
		for(j=0; j<p; j++)
			for(k=0; k<n; k++)
				d[j][k]=INF;
    for(i=0; i<m; i++){
			fscanf(fin, "%d%d", &x, &y);
			vec[y][v[y]++]=x;
			fscanf(fin, "%d", &mat[x][y]);
    }
    fclose(fin);
    d[1][0]=0;
    for(i=0; i<p; i++)
			for(j=0; j<n; j++)
				if(i&(1<<j))
					for(k=0; k<v[j]; k++)
						if(i&(1<<vec[j][k]))
							d[i][j]=minim(d[i][j], d[i^(1<<j)][vec[j][k]]+mat[vec[j][k]][j]);
		i=INF;
		for(j=0; j<v[0]; j++)
			i=minim(i, d[p-1][vec[0][j]]+mat[vec[0][j]][0]);
		fout=fopen("hamilton.out", "w");
		if(i==INF)
			fprintf(fout, "Nu exista solutie\n");
		else
			fprintf(fout, "%d\n", i);
		fclose(fout);
    return 0;
}