#include<fstream>
#define NMAX 20
#define CONFMAX 300000
#define INF 18000010

using namespace std;

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

int n, m, a[NMAX][NMAX], best[CONFMAX][NMAX];

void Init()
{
    int i, j;

    for (i=0; i<CONFMAX; ++i)
        for (j=0; j<NMAX; ++j) best[i][j]=INF;

    for (i=0; i<NMAX; ++i)
        for (j=0; j<NMAX; ++j) a[i][j]=INF;
}

void Citeste()
{
    int x, y, c;

    f>>n>>m;
    while (m--)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }
}

int dinamica(int conf, int nod)
{
    int prec, mn=INF;

    for (prec=0; prec<n; ++prec)
        if (prec!=nod && conf&(1<<prec)!=0 && a[prec][nod]!=INF)
            mn=min(mn, best[conf^(1<<nod)][prec]+a[prec][nod]);
    return mn;
}

void Solve()
{
    int lim=(1<<n), conf, nod;

    best[1][0]=0;
    for (conf=2; conf<lim; ++conf)
        for(nod=1; nod<n; ++nod)
            if (conf&(1<<nod)!=0)
                best[conf][nod]=dinamica(conf, nod);
}

void Scrie()
{
    int i, mn=INF, conf=(1<<n)-1;

    for (i=1; i<n; ++i)
        mn=min(mn, best[conf][i]+a[i][0]);
    if (mn!=INF) g<<mn<<"\n";
    else g<<"Nu exista solutie\n";
}

int main()
{
    Init();

    Citeste();

    Solve();

    Scrie();

    f.close();
    g.close();
    return 0;
}