#include <stdio.h>
#include <vector>
#define IN "hamilton.in"
#define OUT "hamilton.out"
#define N 19
#define oo 0x3f3f3f3f
#define L 1<<19
using namespace std;

int n, m, x, y, c, p;
int Cost[N][N];
int A[L][N];
int Sz, Sol;
vector <int> V[N];

inline int Min(int a,int b)
{
    return a<b?a:b;
}

int main ()
{
    freopen (IN ,"r", stdin);
    freopen (OUT ,"w" ,stdout);

    scanf ("%d %d",&n,&m);
    for (int i=0;i<m;i++)
    {
        scanf ("%d %d %d",&x,&y,&c);
        Cost[x][y]=c;
        V[y].push_back(x);
    }

    Sz=1<<n;
    for (int i=0;i<Sz;i++)
        for (int j=0;j<n;j++)
            A[i][j]=oo;
    A[1][0]=0;

    for (int i=0;i<Sz;i++)
        for (int j=0;j<n;j++)
            if (i&(1<<j))
            {
                p=i^ (1<<j);
                for (int k=0;k<V[j].size();k++)
                    if (i&(1<<V[j][k]))
                        A[i][j]= Min(A[i][j], A[p][V[j][k]] + Cost[V[j][k]][j]);
            }

    Sol=oo;
    for (int i=0;i<V[0].size();i++)
        Sol= Min(Sol, A[Sz-1][V[0][i]] + Cost[V[0][i]][0]);

    if (Sol==oo)
        printf("Nu exista solutie\n");
    else
        printf("%d\n",Sol);

    return 0;
}