#include<stdio.h>
#include<vector>
using namespace std;

FILE *f = fopen("hamilton.in","r");
FILE *g = fopen("hamilton.out","w");

typedef vector<int>::iterator it;

#define MaxN 19
#define Max2maxN ((1<<18)+100)
#define INF (1<<29)
#define sh short int

int N,M;
int Best[MaxN][Max2maxN];
int Cost[MaxN][MaxN];
vector<int> A[MaxN];
int Sol = INF;

void citire(void)
{
    int a,b,c;

    fscanf(f,"%d %d\n",&N,&M);
    for(int i=1;i<=M;i++)
    {
        fscanf(f,"%d %d %d",&a,&b,&c);
        A[a].push_back(b);
        Cost[a][b] = c;
    }
}

void Initializare(void)
{
    for(int i=0;i<N;i++)
        for(int j=(1<<N)-1;j;j--)
            Best[i][j] = INF;

    Best[0][1] = 0;
}

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

void Rezolvare(void)
{
    Initializare();

    for(int i=0;i< 1<<N;i++)
        for(int j=0;j<N;j++)
            if(i & (1<<j))
                for(it k=A[j].begin();k<A[j].end();k++)
                    Best[*k][(1<<(*k))^i] = min(Best[*k][(1<<(*k))^i],Best[j][i] + Cost[j][*k]);

    for(int i=1;i<N;i++)
        if(Cost[i][0] > 0)
            Sol = min(Sol, Best[i][ (1<<N)-1 ]+Cost[i][0]);
}

int main()
{
    citire();
    Rezolvare();

    fprintf(g,(Sol == INF) ? "Nu exista solutie\n" : "%d\n",Sol);
}