#include <fstream>
#include <vector>

using namespace std;
#define INF 100000000
int n,m,i,j,x,y,z,c[262150][19],co[19][19];
int s;
std::vector<int> a[19];
int main()
{
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    f>>n>>m;
    for(i=0; i<n; i++)for(j=0; j<n; j++)co[i][j]=INF;
    for(i=1; i<=m; i++)
    {
        f>>x>>y>>z;
        co[x][y]=z;
        a[y].push_back(x);
    }
    s=(1<<n);
    for(i=0; i<s; ++i)
        for(j=0; j<n; j++)
            c[i][j]=INF;
    c[1][0]=0;
    for(i=0; i<s; ++i)
        for(j=0; j<n; j++)
            if(i&(1<<j))
                for(x=0; x<a[j].size(); x++)
                    if(i&(1<<a[j][x]))
                        c[i][j]=min(c[i][j],c[i^(1<<j)][a[j][x]]+co[a[j][x]][j]);
    s=INF;
    z=(1<<n)-1;
    for(i=0; i<a[0].size(); i++)
        s=min(s,c[z][a[0][i]]+co[a[0][i]][0]);
   if(s==INF)g<< "Nu exista solutie";
   else g<<s;

}