#include <bits/stdc++.h>

#define input "hamilton.in"
#define output "hamilton.out"
#define NMAX 20
#define SMAX 262150
#define inf 100000000

using namespace std;

ifstream in(input);
ofstream out(output);

vector < int > muchii[NMAX];
int cost[NMAX][NMAX], dp[SMAX][NMAX], N, M;

void Init()
{
    for(int i = 0; i <= 1 << N; i++)
        for(int j = 0; j <= N; j++)
            dp[i][j] = inf;
    for(int i = 0; i <= N; i++)
        for(int j = 0; j <= N; j++)
            cost[i][j] = inf;
}

void Read_Data()
{
    in >> N >> M;
    Init();
    for(int i = 1; i <= M; i++)
    {
        int x, y, c; in >> x >> y >> c;
        cost[x][y] = c;
        muchii[y].push_back(x);
    }

}

void Solve()
{
    dp[1][0] = 0;
    int Subs = 1 << N;
    for(int sub = 3; sub < Subs; sub += 2)
        for(int i = 1; i < N; i++)
            if(sub & (1 << i))
                for(unsigned j = 0; j < muchii[i].size(); j++)
                    dp[sub][i] = min(dp[sub][i], dp[(sub ^ (1 << i))][muchii[i][j]] + cost[muchii[i][j]][i]);
    int best_sol = inf;
    for(int i = 1; i < N; i++)
        best_sol = min(best_sol, dp[Subs - 1][i] + cost[i][0]);
    if(best_sol == inf) out << "Nu exista solutie\n";
    else out << best_sol << "\n";
}

int main()
{
    Read_Data();
    Solve();
    return 0;
}