#include <fstream>
#include <iostream>
#include <vector>
#define nmax (1<<20)+5
#define inf 1007483647
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
vector <int> V[20];
int c[nmax][20];
int a[20][20],n,m,s;
int main()
{   fin>>n>>m;
    int i,x,y,z,j,k;

        for(i=0;i<n;++i)
                for(j=0;j<n;++j)
                  a[i][j]=inf;
    for(i=1;i<=m;++i)
    { fin>>x>>y>>z;
        V[y].push_back(x);
        a[x][y]=z;
    }
    for(i=0;i  <(1<<n);++i)
        for(x=0;x<n;++x)
           c[i][x]=inf;

    c[1][0]=0;

       for ( i = 0; i < 1 << n; ++i)
        for ( j = 0; j < n; ++j)
            if (i & (1<<j))
                for ( k = 0; k < V[j].size(); ++k)
                    if (i & (1<<V[j][k]))
                        c[i][j] = min(c[i][j], c[i ^ (1<<j)][ V[j][k] ] + a[ V[j][k] ][j]);
    s=inf;
    for(i=0;i<V[0].size();++i)
        s=min(s,c[(1<<n)-1][V[0][i]]+a[V[0][i]][0] );

        if(s==inf) fout<<"Nu exista solutie";
        else fout<<s;
    return 0;
}