#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

#define DIM 20
#define oo 100000005

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int N,M,Cost[DIM][DIM];
int C[262150][DIM];
vector <int> A[DIM];

void initializare(){
    for(int i=0; i<DIM; ++i)
        for(int j=0; j<DIM; ++j)
            Cost[i][j] = oo;
}

void read(){
    f>>N>>M;
    int x,y,c;
    for(int i=1; i<=M; ++i){
        f>>x>>y>>c;
        A[y].push_back(x);
        Cost[x][y] = c;
    }
}

int calc(int start, int mid, int last){
    if(C[mid][last] == -1){
        C[mid][last] = oo;
        for(int ind=0; ind < A[last].size(); ind++)
            if(mid & (1<<A[last][ind])){
                if (A[last][ind] == start && ((mid ^ (1<<last)) != (1<<start)))
                    continue;
                C[mid][last] = min(C[mid][last], calc(start, mid ^ (1<<last), A[last][ind]) + Cost[A[last][ind]][last]);
            }
    }
    return C[mid][last];
}

int main()
{
    initializare();
    read();
    int sol = oo;
    cout<<sol;
    for(int i=0; i<N; ++i){
        memset(C, -1, sizeof(C));
        C[1 << i][i] = 0;
        for(int j=0; j < A[i].size(); ++j)
            sol = min(sol, calc(i,(1<<N)-1,A[i][j]) + Cost[A[i][j]][i]);
    }
    if(sol == oo) g<<"Nu exista solutie";
    else g<<sol;
}