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

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


const int INF = 1 << 29;

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

int N, M, dp[1 << nmax][nmax];

int minimDe(int nod){

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

    return INF;
}

int main()
{int mask, a, b, c, j, k, i;
    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)
            dp[i][j] = INF;

    dp[1][0] = 0;

    for (mask = 1; mask < (1 << N); ++mask){
        for(j = 0; j < N; ++j){
            if( mask & (1 << j) && dp[mask][j] != INF )
                for(k = 0; k  < graf[j].size(); ++k){
                    int node = graf[j][k].first;
                    int cost = graf[j][k].second;
                    if(! ( mask & (1 << node) ) )
                        dp[ mask | (1 << node) ][node] = min( dp[ mask | (1 << node) ][node], dp[mask][j] + cost );
                }
        }
    }

    int Sol = INF;

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

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

    return 0;
}