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

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

const int N = 19;
const int oo = 0x3f3f3f3f;

int n, msk, cst[N][N];
vector<vector<int>> dp;

void read();

int main()
{
    read();
    dp[0][1] = 0;
    for (int i = 1; i < n; i++)
        dp[i][(1<<i)] = min(dp[i][(1<<i)], cst[0][i]);
    
    for (int m = 1; m < msk; m++){
        vector<int> From, To;
        for (int i = 0; i < n; i++)
            if (m&(1<<i)) From.pb(i);
            else 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;
}

void read(){
    int m; fin >> n >> m;
    msk = (1<<n)-1;
    dp.resize(n, vector<int>(msk+2, oo));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)
            cst[i][j] = oo;
        cst[i][i] = 0;
    }
    while (m--){
        int a, b, c; fin >> a >> b >> c;
        cst[a][b] = min(cst[a][b], c);
    }
}