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

#define inf 200000000
#define Nmax 20
#define Max 262150

int cost[Nmax][Nmax], c[Max][Nmax];
vector < list<int> > vecini;
list <int>::iterator it;

int n, m, sol, lim;

void citire(){
    int x, y, cc;
    scanf("%i %i", &n, &m);

    lim = (1 << n);
    vecini.resize(n+1);

    for(register int i = 0; i < Nmax; ++i)
        for(register int j = 0; j < Nmax; ++j)
            cost[i][j] = inf;
    for(register int i = 0; i < Max; ++i)
        for(register int j = 0; j < Nmax; ++j)
            c[i][j] = inf;

    for(int i = 1; i <= m; ++i){
        scanf("%i %i %i", &x, &y, &cc);
        cost[x][y] = cc;
        vecini[y].push_back(x);
    }
    fclose(stdin);
}

void hamilton(){
    c[1][0] = 0;

    for(register int i = 0; i < lim; ++i)
        for(register int j = 0; j < n; ++j)
            if(i & 1 << j)
                for(it = vecini[j].begin(); it != vecini[j].end(); ++it)
                    if(i & 1 << *it)
                        c[i][j] = min(c[i][j], c[i ^ (1 << j)][*it] + cost[*it][j]);
    sol = inf;
    for(it = vecini[0].begin(); it != vecini[0].end(); ++it)
        sol = min(sol, c[lim - 1][*it] + cost[*it][0]);
    if(sol == inf) printf("Nu exista solutie\n");
        else printf("%i\n", sol);
}

int main(){
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);

    citire();
    hamilton();
}