#include <fstream>
#include <vector>
#define nmax 20
#define valoare 100000000

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");



vector < pair<int, int> > graf[nmax];

int N, M, sir[nmax * 7][nmax];

int minimDe(int nod){
    int minim = valoare;

    for(unsigned i = 0; i < graf[nod].size(); ++i)
        if (graf[nod][i].first == 0)
            minim = graf[nod][i].second;

    return minim;
}

int main()
{int i, a, b, c, j, k;
    f>>N>>M;

    for(i = 1; i <= M; ++i){
        f>>a>>b>>c;
        graf[a].push_back( make_pair(b, c) );
    }

    for(i = 0; i < (1 << N); ++i)
        for(j = 0; j < N; ++j)
            sir[i][j] = valoare;

    sir[1][0] = 0;

    for (i = 1; i < (1 << N); ++i){
        for(j = 0; j < N; ++j){
            if( i & (1 << j) )
                for(k = 0; k  < graf[j].size(); ++k)
                    if(! ( i & (1 << graf[j][k].first) ) )
                        sir[ i | (1 << graf[j][k].first) ][k] = min( sir[ i | (1 << graf[j][k].first) ][k], sir[i][j] + graf[j][k].second );
        }
    }

    int Sol = valoare;

    for (i = 0; i < N; ++i)
        Sol = min(Sol, sir[(1<<N) - 1][ i ] + minimDe(i) );

    if (Sol == valoare) g << "Nu exista solutie" << '\n';
    else g << Sol << '\n';

    return 0;
}