#include<iostream>
#include<fstream>
#include<vector>
#define DN ((1<<18)+20)
#define inf 1000000000
#define s second
#define f first
using namespace std;
fstream fin("hamilton.in",ios::in),fout("hamilton.out",ios::out);
int bst[DN][20],n,m,N;
vector<pair<int,int> > v[20];
int main()
{
    int i,j,k,a,b,c,bit,vecin,val,r=inf;
    fin>>n>>m; N=(1<<n);
    for(i=1;i<=m;i++){
        fin>>a>>b>>c; v[a].push_back({b,c});
    }
    for(i=0;i<=N;i++) for(j=0;j<n;j++) bst[i][j]=inf;
    bst[1][0]=0;
    for(i=1;i<N;i++)
    {
        for(j=0;j<n;j++)
        {
            bit=(1<<j);if((i&bit)==0) continue;//j-ul trebuie sa faca parte din i
            for(k=0;k<v[j].size();k++)
            {
                vecin=v[j][k].f;
                val=v[j][k].s;
                bit=(1<<vecin);
                //vecinul sa nu fie bagat in configuratie deja
                if((i&bit)==0) bst[i+bit][vecin]=min(bst[i+bit][vecin],bst[i][j]+val);
            }
        }
    }
    for(i=1;i<n;i++)
    {
        for(j=0;j<v[i].size();j++)
        {
            vecin=v[i][j].f;
            val=v[i][j].s;
            if(vecin==0)
            {
                r=min(r,bst[N-1][i]+val);
            }
        }
    }
    if(n==1){
        fout<<"0\n";
        return 0;
    }
    if(r==inf)
    {
        fout<<"Nu exista solutie\n";
        return 0;
    }
    fout<<r;
}