#include <fstream>
#include <vector>

using namespace std;

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

const int NMax = 18, oo = 2e9;

vector <int> G[NMax + 5], S;

int DP[(1 << NMax) + 5][NMax + 5], N, M, C[NMax + 5][NMax + 5], Lim, Sol;

int main()
{
    fin >> N >> M; Lim = (1 << N);

    for(int i = 0, a, b, c; i < M; i++)
    {
        fin >> a >> b >> c;

        G[b].push_back(a); C[a][b] = c;

        if(b == 0) S.push_back(a);
    }

    for(int i = 0; i < N; i++)
        for(int j = 0; j < Lim; j++)
            DP[j][i] = oo;

    DP[1][0] = 0, Sol = oo;

    for(int i = 1; i < Lim; i++)
        for(int j = 0; j < N; j++)
            if(i & (1 << j))
            {
                for(auto Vecin : G[j])
                    DP[i][j] = min(DP[i][j], DP[i - (1 << j)][Vecin] + C[Vecin][j]);
            }
    for(auto i : S)
        Sol = min(Sol, DP[Lim - 1][i] + C[i][0]);

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

    fin.close();
    fout.close();

    return 0;
}