# include <fstream>
# include <iostream>
# define infi (1<<30)
# define Nmax 2<<18+5
# define nmax 19
# define min(a,b) ( a < b ?  a : b )
using namespace std;
ifstream fi("hamilton.in");
ofstream fo("hamilton.out");
typedef struct node
{
    int x,y;
    node *next;
}
   *nod;
nod S[nmax];
int s[Nmax][nmax];
int main(void)
{
    int n,m;
    fi>>n>>m;
    int x,y,z,k=1<<n;
    while (m--)
    {
        fi>>x>>y>>z;
        nod p=new node;
        p->x=y;p->y=z;
        p->next=S[x];S[x]=p;
    }
    for (int i=0;i<k;++i)
        for (int j=0;j<n;++j) s[i][j]=infi;
    s[1][0]=0;
    for (int i=0;i<k;++i)
        for (int j=0;j<n;++j)
           if (i & (1<<j))
             {
                 for (nod p=S[j];p;p=p->next)
                    if (i & (1<<p->x))
                       s[i][j]=min(s[i][j],s[i^(1<<j)][p->x]+p->y);
             }
    int sol=infi;
    for (nod p=S[0];p;p=p->next)
           sol=min(sol,s[k-1][p->x]+p->y);
    if (sol==infi) fo<<"Nu exista solutie";else fo<<sol;
    return 0;
}