#include <fstream>
#include <vector>
#include <bitset>
#include <string.h>
#include <algorithm>

using namespace std;

const char infile[] = "hamilton.in";
const char outfile[] = "hamilton.out";

ifstream fin(infile);
ofstream fout(outfile);

const int MAXN = 20;
const int oo = 0x3f3f3f3f;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

int N, M, d[MAXN][MAXN], dp[1 << MAXN][MAXN];
///dp[i][j]  costul minim de a ajunge in nodul j avand deja vizitate bitii de 1 in configuratia binara a lui i
Graph G;

int main() {
    fin >> N >> M;
    for(int i = 1 ; i <= M ; ++ i) {
        int x, y, z;
        fin >> x >> y >> z;
        G[y].push_back(x);
        d[x][y] = z;
    }
    memset(dp, oo, sizeof(dp));
    dp[1][0] = 0;
    for(int i = 0 ; i < (1 << N) ; ++ i)
        for(int j = 0 ; j < N ; ++ j)
            if(i & (1 << j))
                for(It it = G[j].begin(), fin = G[j].end(); it != fin ; ++ it)
                    if(i & ( 1 << *it))
                        dp[i][j] = min(dp[i][j], dp[i ^ ( 1 << j) ][*it] + d[*it][j]);
    int Ans = *min_element(dp[(1 << N)-1], dp[(1 << N)-1] + N) ;
    if(Ans == oo)
        fout << "Nu exista soltuie";
    else fout << Ans << '\n';
    fin.close();
    fout.close();
    return 0;
}