#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const short Nmax = 18;
const int inf = (1 << 25);
int cost[Nmax][Nmax], n, m, dp[Nmax][1 << Nmax], valmax;
int main()
{
    int x, y, valmax, val;
    fin >> n >> m;
    valmax = (1 << n) - 1;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < n ; j++)
            cost[i][j] = inf;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j <= valmax ; j++)
            dp[i][j] = inf;
    while(m -- )
    {
        fin >> x >> y >> val;
        cost[x][y] = val;
    }
    dp[0][1] = 0;
    for(int i = 1 ; i <= valmax ; i++)
        for(int j = 0 ; j < n ; j++)
            if(i & (1 << j))
                for(int k = 0 ; k < n ; k++)
                    if(! (i & (1 << k)))
                    {
                        if(cost[j][k] != inf && dp[k][i | 1 << k] > dp[j][i] + cost[j][k])
                            dp[k][i | 1 << k] = dp[j][i] + cost[j][k];
                    }
    int sol = inf;
    for(int i = 0 ; i < n ; i++)
        sol = min(sol , dp[i][valmax] + cost[i][0]);
    if(sol == inf)
        fout << "Nu exista solutie\n";
    else fout << sol << "\n";
    fin.close();
    fout.close();
    return 0;
}