#include <fstream>
#include <stdlib.h>

using namespace std;

#define DEBUG false
#define MAXN 18
#define MAXSTATES (1<<18)
#define INF 2000000000
#if DEBUG
#include <iostream>
#define INFILE "/Users/biordach/Documents/Xcode Projects/training/training/hamilton.in"
#define __OUT cout
#else
#define INFILE "hamilton.in"
#define OUTFILE "hamilton.out"
ofstream __OUT(OUTFILE);
#endif

int n, m;
int dg[MAXN][MAXN], rg[MAXN][MAXN];// direct/reversed graph
int c[MAXSTATES][MAXN];

void readInput();
void solve();
void printOutput();

int main(int argc, const char * argv[])
{
    readInput();
    solve();
    printOutput();

#if DEBUG == false
    __OUT.close();
#endif
    
    return 0;
}

void readInput(){
    ifstream in(INFILE);
    in>>n>>m;

    for(int i=0; i < m; i++){
        int x, y, z;
        in >> x >> y >> z;
        dg[x][y] = z;
        rg[y][x] = z;
    }
    in.close();
}

int minim(int a, int b){
    return a <=b ? a: b;
}

void normalizare(int &a){
    if(a > INF)
        a = INF;
}
void printState(int state){
    for (int x = 0 ; x < n; x++)
        if(state & 1 << x)
            __OUT<<x<<' ';
    __OUT<<'\n';
}


int calc(int state, int lastnode){

    if(c[state][lastnode] != -1) {
#if DEBUG == true
        __OUT<<"calculate for last node: "<<lastnode << " and state: ";
        printState(state);
        __OUT<<"raspuns: "<< c[state][lastnode]<<'\n';
#endif
        return c[state][lastnode];
    }
    
    c[state][lastnode] = INF;
    for(int i=0; i < n; i++){
        if((state & (1 << i)) && rg[lastnode][i]){
            int x = calc(state - (1 << lastnode), i);
            c[state][lastnode] = minim(c[state][lastnode], x + rg[lastnode][i]);
            normalizare(c[state][lastnode]);
        }
    }

#if DEBUG == true
    __OUT<<"calculate for last node: "<<lastnode << " and state: ";
    printState(state);
    __OUT<<"raspuns: "<< c[state][lastnode]<<'\n';
#endif
    return c[state][lastnode];
}

void solve(){
    for(int i=0; i < n; i++)
        for(int j=0; j < 1<<n;j++ ){
            c[j][i] = -1;
        }

    c[1][0] = 0;
    
    for(int i=0; i < n; i++)
        if(rg[0][i])
            calc((1 << n) - 1, i);
    
}

void printOutput(){
    int sol = INF;
    int x = (1<<n) - 1;
    
    for (int i=0;i<n;i++)
        if(dg[i][0] && c[x][i] < INF){
            if(sol > c[x][i] + dg[i][0])
                sol = c[x][i] + dg[i][0];
        }
    if (sol != INF)
        __OUT<<sol<<'\n';
    else __OUT<<"Nu exista solutie\n";
}