#include <iostream>
#include <fstream>
#include <vector>
#define MAXIM 999999999
using namespace std;
ifstream f1("hamilton.in");
ofstream f2("hamilton.out");
vector<int> listaDeAdiacenta[20];
int cost[20][20],mascaDeBiti[262150][20],n,m;



void rezolvare(){
    for(int j=0;j<(1<<n);j++){
        for(int i=0;i<=n;i++){
            if(j&(1<<i)){
                for(auto &x : listaDeAdiacenta[i]){
                    if(j&(1<<x)){
                        if(mascaDeBiti[j^(1<<i)][x]+cost[x][i]<mascaDeBiti[j][i]){
                            mascaDeBiti[j][i]=mascaDeBiti[j^(1<<i)][x]+cost[x][i];
                        }
                    }
                }
            }
        }
    }
}

void initializare(){
    for(int i=0;i<=19;i++){
        for(int j=0;j<=19;j++){
            cost[i][j]=MAXIM;
        }
    }
    for(int j=0;j<(1<<18);j++){
        for(int i=0;i<=19;i++){
            mascaDeBiti[j][i] = MAXIM;
        }
    }

}

void raspuns(){
    int ultimulRand=(1<<n)-1;
    int minim=MAXIM;
    for(int i=0;i<=n;i++){
        if(mascaDeBiti[ultimulRand][i]+cost[i][0]<minim){
            minim=mascaDeBiti[ultimulRand][i]+cost[i][0];
        }
    }
    if(minim!=MAXIM)
        f2<<minim;
    else
        f2<<"Nu exista solutie";
}

void citire(){
    int x,y;
    f1>>n>>m;
    for(int i=0;i<m;i++){
        f1>>x>>y;
        listaDeAdiacenta[y].push_back(x);
        f1>>cost[x][y];
    }
}

int main() {
    initializare();
    citire();
    mascaDeBiti[1][0]=0;
    rezolvare();
    raspuns();
    return 0;
}