#include <iostream>
#include <stdio.h>
#include <vector>
#define N (1<<19)
#define INF 0x3f3f3f3f
using namespace std;

int n,m;
int cost[21][21],c[N][21];
int a[21][21];
vector < int > A[21];
void citire()
{
    freopen("hamilton.in","r",stdin);
    scanf ("%d%d",&n,&m);
    int x,y,z;
    for (int i=0;i<(1<<n);i++)
        for (int j=0;j<=n;j++)
            cost[i][j]=INF,c[i][j]=INF;



    for (int i=0;i<m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        cost[x][y]=z;
        A[y].push_back(x);
    }

    c[1][0]=0;

    for (int i=0;i<(1<<n);i++)
        for (int j=0;j<n;j++)
             if (i & (1<<j))
                for (int l=0;l<A[j].size();l++)
                    if (i & (1<<A[j][l]))
                        c[i][j]=min(c[i][j],c[i ^ (1<<j) ][A[j][l]]+cost[A[j][l]][j]);

    int Sol = INF;
    for (int i = 0; i < A[0].size(); ++i)
        Sol = min(Sol, c[(1<<n) - 1][ A[0][i] ] + cost[ A[0][i] ][0]);
    freopen ("hamilton.out","w",stdout);
    if (Sol!=INF)
        printf("%d",Sol);
    else
        printf("Nu exista solutie");

   /* int minim=INF;
    for (int j=0;j<n;j++)
        if (a[1<<n-1][j]<minim && a[j][1])
            minim=a[1<<n-1][j];
    cout<<minim;*/
}

int main()
{
    citire();
    return 0;
}