#include <fstream>

using namespace std;

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

const int MAX_N = 18, MAX_COST = 1000000;

int d[1<<MAX_N][MAX_N];
int c[MAX_N][MAX_N];

int main()
{
    int n, m, i, j, k;
    in >> n >> m;
    int nod1, nod2;
    for(i = 0; i < m; i++)
    {
        in >> nod1 >> nod2;
        in >> c[nod1][nod2];
    }
    int limit = (1 << n);
    for(j = 1; j < n; j++)
    {
        d[(1<<j)][j] = c[0][j];
    }
    int minCost = MAX_COST*MAX_N;
    for(i = 3; i < limit; i+=2)
    {
        for(j = 1; j < n; j++)
        {
            if((i >> j)%2== 1)
                for(k = 1; k < n; k++)
                {
                    if(((i >> k)%2 == 1) && (c[k][j] != 0) && (d[i^(1<<j)][k]+c[k][j] < minCost))
                    {
                        minCost = d[i^(1<<j)][k]+c[k][j];
                    }
                }
                if(minCost != MAX_COST*MAX_N)
                    d[i][j] = minCost;
        }
    }
    minCost = MAX_COST*MAX_N;;
    for(j = 0; j < n; j++)
    {
        if(d[(1<<n)-1][j] != MAX_COST*MAX_N && d[(1<<n)-1][j] < minCost)
        {
            minCost = d[(1<<n)-1][j];
        }
    }
    if(minCost != MAX_COST*MAX_N)
        out << minCost;
    else
        out << "Nu exista solutie";
    return 0;
}