#include<fstream>
#define NMAX 20
#define CONFMAX 262154
#define INF 324000000

using namespace std;

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

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

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

    f>>n>>m;

    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }
}

void Initializeaza()
{
    int i, j, lim=(1<<n)-1;

    for (i=0; i<=lim; ++i)
        for (j=0; j<n; ++j) best[i][j]=INF;
}

int recurenta(int conf, int nod)
{
    int i, mn=INF, confp;

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

void Solve()
{
    int conf, m=(1<<n)-1, SOL=INF, i;

    best[1][0]=0;

    for (conf=2; conf<=m; ++conf)
        for (i=0; i<n; ++i)
            best[conf][i]=min(best[conf][i], recurenta(conf, i));

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

int main()
{
    Citeste();
    Initializeaza();
    Solve();
    f.close();
    g.close();
    return 0;
}