#include <fstream>
#include <vector>

using namespace std;

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

const int inf= 1<<28;
const int nmax= 18;
const int pmax= 1<<nmax;

int d[pmax][nmax], c[nmax][nmax];

vector <int> g[nmax];

int main(  ) {
    for ( int i= 0; i<nmax; ++i ) {
        for ( int j= 0; j<nmax; ++j ) {
            c[i][j]= inf;
        }
    }
    for ( int i= 0; i<pmax; ++i ) {
        for ( int j= 0; j<nmax; ++j ) {
            d[i][j]= inf;
        }
    }
    d[1][0]= 0;

    int n, m;
    fin>>n>>m;
    for ( int i= 0; i<m; ++i ) {
        int x, y, z;
        fin>>x>>y>>z;

        g[y].push_back(x);
        c[x][y]= z;
    }

    for ( int i= 0; i<(1<<n); ++i ) {
        for ( int j= 0; j<n; ++j )
            if ( (i&(1<<j))!=0 ) {
                for ( vector <int>::iterator it= g[j].begin(); it!=g[j].end(); ++it ) {
                    if ( (i&(1<<*it))!=0 ) {
                        d[i][j]= min(d[i][j], d[i-(1<<j)][*it]+c[*it][j]);
                    }
                }
            }
    }

    int sol= inf;
    for ( vector <int>::iterator it= g[0].begin(); it!=g[0].end(); ++it ) {
        sol= min(sol, d[(1<<n)-1][*it]+c[*it][0]);
    }

    if ( sol==inf ) {
        fout<<"Nu exista solutie\n";
    } else fout<<sol<<"\n";

    return 0;
}