#include <bits/stdc++.h>
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
const short Nmax = 18;
const int inf = (1 << 20);
int c[Nmax][Nmax] , dp[Nmax][1 << Nmax] , n , m , vmax;
/**
    dp[i][j] - costul minim de la nodul 1  la nodul i trecand prin j valori binare(bitul j = 1 inseamna
                ca am trecut prin nodul j)
*/
int main()
{
    int x , y , val;
    fin >> n >> m;
    vmax = (1 << n) - 1;
    for(int i = 0 ; i < n ; i++)
        for(int j = 1 ; j <= vmax ; j++)
            dp[i][j] = inf;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < n ; j++)
            c[i][j] = inf;
    for(int i = 1 ; i <= m ; i++)
    {
        fin >> x >> y >> val;
        c[x][y] = val;
    }
    dp[0][1] = 0;
    for(int i = 1 ; i <= vmax ; i++)
        for(int j = 0 ; j < n ; j++)
            if(( i & (1 << j)) > 0)
                for(int k = 0 ; k < n ; k++)
                    if((i & (1 << k)) == 0)
                        dp[k][i | (1 << k)] = min(dp[k][i | (1 << k)] , dp[j][i] + c[j][k]);
    int mn = inf;
    for(int i = 0 ; i < n ; i++)
        mn = min(mn , dp[i][vmax] + c[i][0]);
    if(mn == inf)
        fout << "Nu exista solutie\n";
    else fout << mn << "\n";
    fin.close();
    fout.close();
    return 0;
}