#include <stdio.h>
#include <vector>
#include <string.h>
#define TR(C, i)\
    for(i = C.begin(); i < C.end(); i++)
#define pb push_back

const int oo = 0x3f3f3f3f;
const int nmax = 20;
int C[ (1 << (nmax - 2)) + 10][nmax];
int Cost[nmax][nmax], N, M;

using namespace std;
vector <int> G[nmax];

void read()
{
    freopen ("hamilton.in","r",stdin);
    freopen ("hamilton.out","w",stdout);

    scanf("%d %d", &N, &M);
    int i, a, b, s;
    for(i = 1; i <= M; i++)
    {
        scanf("%d %d %d", &a, &b, &s);
        G[b].pb( a );
        Cost[a][b] = s;
    }
}

int main()
{
    memset(C, 0x3f, sizeof(C));
    memset(Cost, 0x3f, sizeof(Cost));

    read();

    int i, j;
    vector<int>::iterator it;
    C[1][0] = 0;
    for(i = 0; i < ( 1 << N ); i++)
        for(j = 0; j < N; j++)
            if(i & (1 << j))
                TR(G[j],it)
                    if(i & (1 << (*it)))
                        C[i][j] = min(C[i][j], C[i ^ (1 << j)][*it] + Cost[*it][j]);

    int Sol = oo;
    TR(G[0],it)
        Sol = min(Sol, C[(1 << N) - 1][*it] + Cost[*it][0]);

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