#include <iostream>
#include <fstream>
#define NMAX 18
#define INF (1 << 30)

using namespace std;

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

int N, M, mat[20][20];
long long d[1 << NMAX][NMAX];

inline long long minim(int a, int b){
    if(a < b){
        return a;
    }
    return b;
}

int main(){

    int i, i1, j, j2, k, k2;
    int x, y, c;
    in >> N >> M;
    for(i = 1; i <= M; i++){
        in >> x >> y >> c;
        //x++; y++;
        mat[x][y] = c;
    }
    int nrPerechi = (1 << N) - 1;
    for(i = 1; i < N; i++){
        d[1][i] = INF;
    }
    for(i = 3; i <= nrPerechi; i += 2){
        d[i][0] = INF;
        for(j = 1; j < N; j++){
            d[i][j] = INF;
            j2 = (1 << j);
            if(i & j2){
                i1 = i ^ j2;
                for(k = 0; k < N; k++){
                    k2 = 1 << k;
                    if( (i1 & k2) && j != k && mat[k][j] != 0){
                        d[i][j] = minim(d[i1][k] + mat[k][j], d[i][j]);
                    }
                }
            }
        }
    }
    int m = INF;
    for(i = 1; i < N; i++){
        if(mat[i][0] != 0){
            m = minim(m, d[nrPerechi][i] + mat[i][0]);
        }
    }
    if(m != INF){
        out << m;
    }else{
         out<<"Nu exista solutie";
    }
    return 0;
}