#include <fstream>
#include <vector>

using namespace std;

unsigned short int N, M;
unsigned short int x, y;
unsigned int c;

vector <int> v[20];
int cost[20][20];
int sol[(1<<19)][20];
const int INF=1<<29;
int i, j, k;
int con;

int solution;

int main ()
{
    ifstream fin ("hamilton.in");
    fin >> N >> M;
    while (M)
    {
        fin >> x >> y >> c;
        v[y].push_back(x);
        cost[x][y] = c;
        M--;
    }
    fin.close();
    for (i=0; i<(1<<N); i++)
        for (j=0; j<N; j++)
            sol[i][j] = INF;
    sol[1][0] = 0;
    for (i=0; i<(1<<N); i++)
        for (j=0; j<N; j++)
            if (i&(1<<j))
            {
                con = v[j].size();
                for (k=0; k<con; k++)
                    sol[i][j] = min(sol[i^(1<<j)][v[j][k]]+cost[v[j][k]][j],sol[i][j]);
            }
    solution = INF;
    con = v[0].size();
    for (i=0; i<con; i++)
        solution = min(solution,sol[(1<<N)-1][v[0][i]]+cost[v[0][i]][0]);
    ofstream fout ("hamilton.out");
    if (solution != INF)
        fout << solution;
    else
        fout << "Nu exista solutie";
    fout.close();
    return 0;
}