#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define pb push_back

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

const int NMAX = 18;
const int MMAX = (1<<18);
const int oo = 0x3f3f3f3f;

int n, m, dp[NMAX][MMAX], cst[NMAX][NMAX];

int main()
{   
    fin >> n >> m;
    for (int i = 0; i < n; i++) {
        memset(dp[i], oo, sizeof dp[i]);
        memset(cst[i], oo, sizeof cst[i]);
    }

    while (m--){
        int a, b, c; 
        fin >> a >> b >> c;
        cst[a][b] = c;
    }
    
    dp[0][1] = 0;
    for (int i = 1; i < n; i++)
        dp[i][(1<<i)] = cst[0][i];

    int msk = (1<<n)-1;
    for (m = 1; m < msk; m++){
        vector<int> From, To;
        for (int i = 0; i < n; i++)
            (m&(1<<i)) ? From.pb(i) : To.pb(i);
        for (auto from: From)
            for (auto to: To){
                int nm = (m | (1<<to));
                dp[to][nm] = min(dp[to][nm], dp[from][m] + cst[from][to]);
            }
    }

    if (dp[0][msk] == oo) fout << "Nu exista solutie";
    else fout << dp[0][msk];

    return 0;
}