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

int n,m;
int cost[20][20],c[N][20];
int a[20][20];
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][x]=1;
    }

    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<n;l++)
                    if (a[j][l] && (i & (1<<l)))
                        c[i][j]=min(c[i][j],c[i ^ (1<<j) ][l]+cost[l][j]);

     /*   for (int i=0;i<(1<<n);i++)
    {
        for (int j=0;j<n;j++)
            cout<<c[i][j]<<" ";
        cout<<"\n";
    }*/

    int minim=INF;
    for (int j=0;j<n;j++)
        if (c[(1<<n)-1][j]+cost[a[0][j]][0]<minim)
            minim=c[(1<<n)-1][j]+cost[a[0][j]][0];
    freopen("hamilton.out","w",stdout);
    if (minim!=INF)
        printf("%d",minim);
    else
        printf("Nu exista solutie");
}

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