#include <fstream>
#include <vector>
#define nmax 20
#define inf 18000005
using namespace std;
fstream f1("hamilton.in", ios::in);
fstream f2("hamilton.out", ios::out);
int n, m, ct[nmax][nmax], cost[nmax][524288], rez=inf;
vector <int> v[nmax];
void citire()
{
    int i, j, x, y, c;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            ct[i][j]=inf;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        ct[x][y]=c;
        v[y].push_back(x);///retii graful transpus
    }
}
void pd()
{
    int i, j, nod;
    //init:
    for(i=0; i<n; i++)
        for(j=0; j<(1<<n); j++)
            cost[i][j]=inf;
    /*for(i=0; i<n; i++)
        cost[i][(1<<i)]=0; ///lanturi cu un nod*/
    cost[0][1]=0;

    for(j=0; j<(1<<n); j++)
        for(i=0; i<n; i++)
            if(j&(1<<i))
        {
            ///daca nodul final i apare in configuratia j
            for(auto it=v[i].begin(); it!=v[i].end(); ++it)
                if(j&(1<<(*it)))
            {
                nod=*it;///exista muchie de la v la i
                cost[i][j]=min(cost[i][j], cost[nod][j^(1<<i)]+ ct[nod][i]);
            }

        }

    for(auto it=v[0].begin(); it!=v[0].end(); ++it)
        rez=min(rez, cost[*it][(1<<n)-1]+ ct[*it][0]);

    if(rez==inf) f2<< "Nu exista solutie" <<"\n";
    else f2<<rez<<"\n";
}
int main()
{
    citire();
    pd();
    return 0;
}