#include <fstream>
#include <vector>
#include <iostream>
#define nmax 20
#define inf 1 << 29

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


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

int N, M, sir[1 << 20][nmax];

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

    for(int 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] = inf;

    sir[1][0] = 0;

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

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

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

    return 0;
}