#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 a[MAXN][MAXN];
int c[MAXSTATES][MAXN];

struct queue{
    char last;
    int state, cost;
    queue* next;
}*first, *last;

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;
        a[x][y] = z;
    }
    in.close();
}


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

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

    // starding node: 0
    queue* q = new queue;
    q->last = 0;
    q->state = 1;
    q->cost = 0;
    q->next = NULL;
    first = last = q;
    for(;first;first = first -> next){
        if(c[first->state][first->last] < first->cost){
            continue;
        }
        
        for(int i=0;i<n;i++){
            if(!(first -> state & (1 << i)) && a[first->last][i]){
                int newstate = first->state | (1 << i);
                int newcost = first->cost + a[first->last][i];
#if DEBUG
                __OUT<<"old state: ";
                printState(first->state);
                __OUT<<i<<" newstate: ";
                printState(newstate);
                __OUT<<first->cost<<' '<<newcost << ' ' <<c[newstate][i]<<'\n';
                __OUT<<"----------------------------------------\n";
#endif
                if (c[newstate][i] > newcost){
                    c[newstate][i] = newcost;
                    q = new queue;
                    q->state = newstate;
                    q->cost = newcost;
                    q->last = i;
                    q->next = NULL;
                    last->next = q;
                    last = q;
                }
            }
        }
    }
    
}

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