#include <fstream>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

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

const int MAXN = 20;
const int MAX = 1<<18;
const int Inf = 0x3f3f3f3f;
using VI = vector<int>;
VI G[MAXN];
int N, M;
int D[MAX][MAXN];
int C[MAXN][MAXN];

void ReadGraph();
void Solve();

int main()
{
    ReadGraph();
    Solve();

    fin.close();
    fout.close();
    return 0;
}

void ReadGraph()
{
    int x, y, z;

    fin >> N >> M;
    while ( M-- )
    {
        fin >> x >> y >> z;

        G[y].push_back(x);
        C[x][y] = z;
    }
}

void Solve()
{
    int i, j;

    for ( i = 0; i < (1<<N); ++i )
        for ( j = 0; j < N; ++j )
            D[i][j] = Inf;

    D[1][0] = 0;
    for ( i = 0; i < (1<<N); ++i )
        for ( j = 0; j < N; ++j )
            if ( (1<<j)&i )
                for ( const int& t : G[j] )
                    if ( i & (1<<t) )
                        D[i][j] = min( D[i][j], D[i ^ (1<<j)][t] + C[t][j] );

    int rez = Inf;
    for ( const int& x : G[0] )
        rez = min( rez, D[(1<<N) - 1][x] + C[x][0] );

    if ( rez < Inf )
        fout << rez << '\n';
    else
        fout << "Nu exista solutie" << '\n';
}