#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];
int cost[MAXN][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][0]++;
        dg[x][dg[x][0]] = y;
        
        rg[y][0]++;
        rg[y][rg[y][0]] = x;
        
        cost[x][y] = z;
    }
    in.close();
}

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

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=1; i <= rg[lastnode][0]; i++){
        if((state & (1 << rg[lastnode][i]))){
            
            int qq = state - (1 << lastnode);
            
            int x;
            if (c[qq][rg[lastnode][i]] == -1)
                x = calc(qq, rg[lastnode][i]);
            else if (c[qq][rg[lastnode][i]] == INF)
                continue;
            else x = c[qq][rg[lastnode][i]];

            c[state][lastnode] = minim(c[state][lastnode], x + cost[rg[lastnode][i]][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=1; i <= rg[0][0]; i++)
        calc((1 << n) - 1, rg[0][i]);
    
}

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