#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");

#define MAXN 25
#define INFTY 100000000

vector <int> edge[MAXN];
int N, M;

int CostMatrix[MAXN][MAXN];
int DP[MAXN][MAXN];

int main()
{
    fin >>N >>M;

    for (int i = 0; i <= N; ++i)
		for (int j = 0; j <= N; ++j)
			CostMatrix[i][j] = INFTY;

	for (int i = 0; i < M; ++i)
	{
		int x,y;
		fin >>x >>y;
		edge[y].push_back(x);
		fin >>CostMatrix[x][y];
	}

	for (int i = 0; i < (1<<N); ++i)
		for (int j = 0; j <= N; ++j)
			DP[i][j] = INFTY;

	DP[1][0] = 0;
	for (int i = 0; i < (1<<N); ++i)
		for (int j = 0; j < N; ++j)
			if (i & (1<<j))
				for (int k = 0; k < edge[j].size(); ++k)
					if (i & (1<<edge[j][k]))
						DP[i][j] = min(DP[i ^ (1<<j)][edge[j][k]] + CostMatrix[edge[j][k]][j],
											DP[i][j]);

	int final_cost = INFTY;
    for (int i = 0; i < edge[0].size(); ++i)
        final_cost = min(final_cost,
						DP[(1<<N) - 1][edge[0][i]] + CostMatrix[edge[0][i]][0]);

    if (final_cost == INFTY)
		fout <<"Nu exista solutie" <<'\n';
    else
		fout <<final_cost <<'\n';

    return 0;
}