#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
#define Inf 0x3f3f3f
vector< vector< pair<int, int> > > G;
vector< vector<int> > c;
vector< pair<int, int> > LastV;
int N, M;
int main()
{
fin >> N >> M;
G = vector< vector< pair<int, int> > >(N);
c = vector< vector<int> >((1 << N) + 1, vector<int>(N, Inf));
for (int i = 0, x, y, w; i < M; i ++)
{
fin >> x >> y >> w;
G[x].push_back({y, w});
if (y == 0)LastV.push_back({x, w});
}
// initialization
//for (int i = 0; i < N; i ++)
// c[1 << i][i] = 0;
c[1][0] = 0;
int k, w;
for (int a = 1; a < (1 << N); a ++)
for (int i = 0; i < N; i ++)
if (a & (1 << i))
for (int j = 0; j < G[i].size(); j ++)
{
k = G[i][j].first;
w = G[i][j].second;
if (!(a & (1 << k)))
c[a + (1 << k)][k] = min(c[a + (1 << k)][k], c[a][i] + w);
}
int Rez = Inf;
for (int i = 0; i < LastV.size(); i ++)
{
k = LastV[i].first;
w = LastV[i].second;
Rez = min(Rez, c[(1 << N) - 1][k] + w);
}
if (Rez == Inf)fout << "Nu exista solutie";
else fout << Rez;
return 0;
}