#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 25
#define NMAX2 (1<<20)+5
#define INF 0x3f3f3f3f

using namespace std;

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

int d[NMAX2][NMAX]; ///costul minim trecand prin nodurile aratate de i si destinatia in j
int c[NMAX][NMAX]; ///retine costurile pt muchii
vector<vector<int>> gr;
int n,m;
int x,y,cost;
int main()
{
    fin >> n >> m;
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            c[i][j]=INF;
        }
    }
    gr.resize(n+1);
    for(int i=1; i<=m; ++i){
        fin >> x >> y >> cost; ///arc intre x si y cu cost
        gr[y].push_back(x); ///retin graful inversat
        c[x][y]=cost;
    }
    for(int i=0; i<(1<<n); ++i){
        for(int j=0; j<n; ++j){
            d[i][j]=INF;
        }
    }
    d[1][0]=0;
    for(int i=0; i<(1<<n); ++i){
        for(int j=0; j<n; ++j){
            if(i & (1<<j)){
                for (int k = 0; k < gr[j].size(); ++k){
                    if(i & (1<<gr[j][k])){
                        d[i][j] = min(d[i][j], d[i ^ (1 << j)][gr[j][k]] + c[gr[j][k]][j]);
                    }
                }
            }
        }
    }
    int ans=INF;
     for (int i = 0; i < gr[0].size(); ++i){
        ans = min(ans, d[(1 << n) - 1][gr[0][i]] + c[gr[0][i]][0]);
    }
    if(ans==INF){
        fout << "Nu exista solutie" << '\n';
    }
    else{
        fout << ans << '\n';
    }
    return 0;
}