#include <bits/stdc++.h>
#define nmax 19
using namespace std;

ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");

vector<int> G[nmax];
int n,c[nmax][nmax],d[1<<(nmax-1)][nmax],mini=INT_MAX,m;

int main()
{
    int a,b,co;
    fin>>n>>m;
    memset(c,-1,sizeof(c));
    for(int i=1;i<=m;++i){
        fin>>a>>b>>co;
        G[a].push_back(b);
        c[a][b]=co;
    }
    memset(d,-1,sizeof(d));
    d[1][0]=0;
    for(int i=1;i < 1<<n;++i)
        for(int j=0;j<n;++j)
            if((i & 1<<j)&&(d[i][j]!=-1))
                for(vector<int>::iterator it=G[j].begin();it!=G[j].end();++it)
                    if((i & 1<<(*it)) ==0)
                        if(d[i|1<<(*it)][*it]==-1)
                            d[i|1<<(*it)][*it]=d[i][j]+c[j][*it];
                        else
                            d[i|1<<(*it)][*it]=min(d[i|1<<(*it)][*it],d[i][j]+c[j][*it]);
    for(int i=0;i<n;++i)
        if(c[i][0]!=-1)
            mini=min(mini,d[(1<<n)-1][i]+c[i][0]);
    if(mini==INT_MAX)fout<<"Nu exista solutie\n";
    else fout<<mini<<endl;
    return 0;
}