#include <iostream>
#include <fstream>
#include <vector>

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

const int Nmax=19, oo=100000000;
vector <int> G[Nmax];
int din[(1<<18)+5][19], cost[19][19], n, m, i, x, y, z, j, sol;

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        G[y].push_back(x);
        cost[x][y]=z;
    }
    for(i = 0; i < (1<<n); i++)
        for(j = 0; j < n; j++)
            din[i][j]=oo;
    din[1][0]=0;
    for(i = 0; i < (1<<n); i++)
    {
        for(j = 0; j < n; j++)
        {
            if(i & (1<<j))
            {
                for(unsigned int k = 0; k < G[j].size(); k++)
                {
                    if(i & (1<< G[j][k]))
                        din[i][j]=min(din[i][j], din[i ^ (1<<j)][ G[j][k] ]+cost[ G[j][k] ][j]);
                }
            }
        }
    }
    sol=oo;
    for(unsigned int i = 0; i < G[0].size(); i++)
    {
        sol=min(sol, din[(1<<n)-1][ G[0][i] ]+ cost[ G[0][i] ][0]);
    }
    if(sol==oo)
        fout<<"Nu exista solutie";
    else
        fout<<sol;
    return 0;
}