#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 19, MMAX = 19*19, INF = 1e9;

int N, M, cost[NMAX][NMAX], dp[MMAX][NMAX];
vector<int> G[NMAX];

int main ()
{
    fin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cost[i][j] = INF;
        }
    }
    for (int i = 0; i < (1 << N); i++) // 1 << N = 1 * 2^(N) = 1 * pow(2, N)
    {
        for (int j = 0; j < N; j++)
        {
            dp[i][j] = INF;
        }
    }
    for(int i = 0; i < M; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = min(cost[x][y], c);
        G[y].push_back(x);
    }

    dp[1][0] = 0;
    for (int i = 0; i < (1 << N); i++)
    {
        for (int j = 0; j < N; j++)
        {
            if ((i & (1 << j)) != 0)
            {
                for (auto f : G[j])
                {
                    if ((i & (1 << f)) != 0)
                    {
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][f] + cost[f][j]);
                    }
                }
            }
        }
    }
    int rezultat = INF;
    for (auto f : G[0])
    {
        rezultat = min(rezultat, dp[(1 << N) - 1][f] + cost[f][0]);
    }
    if (rezultat == INF)
    {
        fout << "Nu exista solutie";
        return 0;
    }
    fout << rezultat;
    fin.close();
    fout.close();
    return 0;
}