#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMax = 19;
const int inf = 0x3f3f3f3f;
const int Xmax = 262151;
int cst[NMax][NMax];
int dp[Xmax][NMax];

vector < int > G[NMax];
int N, M;

void Read()
{
    fin >> N >> M;

    for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            cst[i][j] = inf;

    for(int i=1; i<=M; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        cst[x][y] = c;
        G[y].push_back(x);
    }
}

int main()
{
    Read();

    for(int i=0; i < (1<<N); ++i)
        for(int j=0; j<N; ++j)
            dp[i][j] = inf;

    dp[1][0] = 0;

    for(int i=0; i < (1<<N); ++i)
        for(int j=0; j < N; ++j)
            if(i & (1<<j))
                for(int k=0; k < G[j].size(); ++k)
                    if(i&(1<<G[j][k]))
                        dp[i][j] = min(dp[i][j],
                                       dp[i^(1<<j)][G[j][k]] +
                                       cst[G[j][k]][j]);

    int Sol = inf;

    for (int i = 0; i<G[0].size(); ++i)
        Sol = min(Sol, dp[(1<<N)-1][G[0][i]] + cst[G[0][i]][0]);

    if (Sol == inf)
        fout << "Nu exista solutie\n";
    else
        fout << Sol;

    return 0;
}