#include <bits/stdc++.h>
#define nmax 19
#define inf 1000000000
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=inf,m;

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