#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int MAXN = 20;
const int INF = 1000000000;
int N, M, Sol;
vector <int> A[MAXN], C[MAXN];
int U[MAXN];
void DFS(int nod, int nr, int cost){
	U[nod] = 1;
	for(size_t i = 0; i < A[nod].size(); ++i){
		if(!U[A[nod][i]])
            DFS(A[nod][i], nr + 1, cost + C[nod][i]);
		if(nr == N && A[nod][i] == 0)
		    Sol = min(Sol, cost + C[nod][i]);
	}
	U[nod] = 0;
}
int main(){
	Sol = INF;
	fin >> N >> M;
	for(int i = 1; i <= M; ++i){
		int x, y, c;
		fin >> x >> y >> c;
		A[x].push_back(y);
		C[x].push_back(c);
	}
	DFS(0, 1, 0);
	if(Sol == INF)
        fout << "Nu exista solutie" << endl;
	else
	    fout << Sol << endl;
	return 0;
}