#include <fstream>
#include <vector>
#define oo int(2e9)
using namespace std;

int conf, n, m, i, j, x, y, c;
vector<int> GT[20];
vector<int> :: iterator it;
int C[270000][18], Cost[18][18], sol;

int main()
{
    ifstream fi("hamilton.in");
    ofstream fo("hamilton.out");
    fi >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fi >> x >> y >> c;
        GT[y].push_back(x);
        Cost[x][y] = c;
    }
    C[1][0] = 0;
    for(conf = 2; conf < (1<<n); conf++)
        for(i = 0; i < n; i++)
        if((1<<i) & conf)
        {
            C[conf][i] = oo;
            for(it = GT[i].begin(); it != GT[i].end(); ++it)
            {
                j = *it;
                if(((1<<j) & conf))
                C[conf][i] = min(C[conf][i], C[conf ^ (1<<i)][j] + Cost[j][i]);
            }
        }
    sol = oo;
    conf = (1<<n) - 1;
    for(i = 1; i < n; i++)
        if(Cost[i][0]) sol = min(sol, C[conf][i] + Cost[i][0]);
    if(sol == oo) fo << "Nu exista solutie\n"; else
    fo << sol << "\n";
    return 0;
}