#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define st first
#define nd second

using namespace std;

const int lg  = 19;
const int Dim = 1 << lg;
const int INF = 0x3f3f3f3f;

int N,M,Sol,Path[Dim][lg];
vector< pair< int,int > > G[Dim];

int Min(int A,int B)
{
    return (A < B) ? A : B;
}

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

     fin >> N >> M;

     for (int i = 1;i <= M;i++)
     {
         int A,B,C;
         fin >> A >> B >> C;
         G[A].pb(mp(B,C));
     }

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

     Path[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 < G[j].size();k++)
               if (i & (1 << G[j][k].st))
                 Path[i][j] = Min(Path[i][j],Path[i ^ (1 << j)][G[j][k].st] + G[j][k].nd);

     Sol = INF;

     for (int i = 0;i < G[0].size();i++)
        Sol = Min(Sol,Path[(1 << N) - 1][G[0][i].st] + G[0][i].nd);

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

    return 0;
}