#include <fstream>
#include <vector>

using namespace std;

const int MAXN = 20;
const int MAXX = 262150;
const int INF = 100000000;

int N, M, Sol;
int Cost[MAXN][MAXN];
int C[MAXX][MAXN];
vector <int> A[MAXN];

int main()
{
	ifstream f("hamilton.in");
	ofstream g("hamilton.out");

	f >> N >> M;

	for(int i=0;i<N;++i)
        for(int j=0;j<N;++j)
         Cost[i][j] = INF;

    for(int i=0;i<(1<<N);++i)
        for(int j=0;j<N;++j)
         C[i][j] = INF;

    for(int i=0;i<M;++i){
        int x,y;
        f >> x >> y;
        A[y].push_back(x);
        f >> Cost[x][y];
    }

	C[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<A[j].size();++k)
            if(i&(1<<A[j][k]))
             C[i][j] = min(C[i][j], C[i^(1<<j)][A[j][k]] + Cost[A[j][k]][j]);


	Sol = INF;
	for (size_t i = 0; i < A[0].size(); ++i)
		Sol = min(Sol, C[(1<<N) - 1][ A[0][i] ] + Cost[ A[0][i] ][0]);

    if(Sol==INF) g << "Nu exista solutie\n";
    else g << Sol;

    return 0;
}