#include<fstream>
#include<vector>
#define NMAX 300000
#define MMAX 20
#define INF 20000000

using namespace std;

int n, m, a[MMAX][MMAX], best[MMAX][NMAX];
vector<int> A[NMAX];
ifstream f("hamilton.in");
ofstream g("hamilton.out");

void Citeste()
{
    int i, x, y, c, j;
    f>>n>>m;
    for (i=0; i<n; ++i)
        for (j=0; j<n; ++j)
            a[i][j]=INF;
    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>c;
        a[x][y]=c;
        A[y].push_back(x);
    }
}

void Initializeaza()
{
    int i, conf;
    for (i=0; i<n; ++i)
        for (conf=1; conf<(1<<n); ++conf)
            best[i][conf]=INF;
    best[0][1]=0;
}

void Solve()
{
    int conf, nod, prec, confp, mn=INF, i;

    for (conf=1; conf<(1<<n); ++conf)
        for (nod=0; nod<n; ++nod)
            if ( (conf & (1<<nod)) )
            {
                for (prec=0; prec<n; ++prec)
                    if ((conf & (1<<prec)))
                    {
                        confp=conf^(1<<nod);
                        best[nod][conf]=min(best[nod][conf], best[prec][confp]+a[prec][nod]);
                    }
            }
    for (i=0; i<A[0].size(); ++i)
    {
        nod=A[0][i];
        mn=min(mn, best[nod][(1<<n)-1]+a[nod][0]);
    }

    if (mn==INF) g<<"Nu exista solutie";
    else g<<mn<<"\n";
}

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