#include<fstream>
#include<vector>
#include<string.h>

using namespace std;

#define min(a,b) (a>b ? b : a)
#define nmax 20

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

const int inf = 1<<30;

int N, cost[nmax][nmax], M;
vector <int> G[nmax];
int C[1<<18][nmax];

int hamilton(int conf, int last)//conectez sau determin drumul de configuratia actuala(conf) cu nodul last
{
    if(C[conf][last] == -1)
    {
        C[conf][last] = inf;
        for(int i = 0; i < G[last].size(); i++)
        {
            int  nod = G[last][i];
            if(conf & (1<<nod) )//daca exista in configuratia actuala un nod cu drum catre last
            {
                if(nod == 0 && conf != (1<<(last)) + 1) continue;//nodul 0 trebuie bagat ultimul

                    C[conf][last] =  min(C[conf][last] , hamilton(conf ^ (1<<last), nod) + cost[nod][last] );

            }

        }
    }
    return C[conf][last];
}
void read()
{
    int x, y;
    fin >>N >> M;

    for(int i = 1; i <= M ;i++)
    {
        int c;
        fin >>x >> y >>c;
        G[y].push_back(x);
        cost[x][y] = c ;

    }
}
int main()
{
    int sol = inf;

    memset(C, -1,sizeof(C));

    for(int i = 0; i < N ;i++)
        for(int j = 0; j < N ;j++)
            cost[i][j] = inf;

    read();
    C[1][0] = 0;
    for(int i = 0; i < G[0].size(); i++)
        sol= min(sol, hamilton( ((1<<N) -1 ), G[0][i]) + cost[G[0][i]][0]);
    if (sol == inf) fout << "Nu exista solutie" << endl;
    else

    fout << sol ;
    fin.close();
    return 0;
}