#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

const int MAXN = 20;
const int INF = 1 << 30;

const int MAXCONFIGURATIE = 262150;

vector<int> vecini[MAXN];
int cost[MAXN][MAXN];
int d[MAXCONFIGURATIE][MAXN];//d[i][j] = costul minim al unui lant ce se termina in nodul j
                  //          si contine toate nodurile identificate cu 1
                  //          in configuratia binara a lui i exact o singura data
int rasp;
int n;
void citire()
{
    int m;

    in >> n >> m;
    for (int i = 0;i < MAXN;++i)
        for (int j = 0;j < MAXN;++j)
            cost[i][j] = INF;
    for (int i = 1;i <= m;++i)
    {
        int x,y,c;
        in >> x >> y >> c;
        vecini[y].push_back(x);//retinem arcul invers
        cost[x][y] = c;
    }
}

int calculare(int configuratie, int ultim)
{
    if(d[configuratie][ultim] != -1)
        return d[configuratie][ultim];

    d[configuratie][ultim] = INF;
    //parcurg nodurile care indica spre acest ultim nod
    for (unsigned int i = 0;i < vecini[ultim].size();++i)
    {
        int vecin = vecini[ultim][i];
        if(configuratie & (1 << vecin))//aleg doar cele care apartin lantului
        {
            //nodul 0 trebuie scos ultimul
            if(vecin == 0 && configuratie != (1 << ultim) + 1)
                continue;
            int x = calculare(configuratie ^ (1 << ultim), vecin) + cost[vecin][ultim];
            if (x < d[configuratie][ultim])
                d[configuratie][ultim] = x;
        }
    }
    return d[configuratie][ultim];
}

void dinamica()
{
    for (int i = 0;i < MAXCONFIGURATIE;++i)
        for (int j = 0;j < MAXN;++j)
            d[i][j] = -1;
    d[1][0] = 0;
    rasp = INF;
    for (unsigned int i = 0;i < vecini[0].size();++i)
    {
        int vecin = vecini[0][i];
        int x = calculare((1 << n) - 1, vecin) + cost[vecin][0];
        if (x < rasp)
            rasp = x;
    }
}

int main()
{
    citire();
    dinamica();
    if (rasp == INF)
        out << "Nu exista solutie" << '\n';
    else out << rasp << '\n';
    return 0;
}