#include <bits/stdc++.h>
using namespace std;
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 oo = 0x3f3f3f3f;

int n;
int cst[18][18];
vector<vector<int>> dp;
void read();

int main()
{
    read();
    int msk = (1<<n) - 1;
    dp.resize(n, vector<int>(msk + 1, oo));
    dp[0][1] = 0;
    for (int i = 1; i < n; i++)
        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++)
            (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;
}

void read(){
    int m; fin >> n >> m;
    for (int i = 0; i < n; i++)
        memset(cst[i], oo, sizeof cst[i]);
    for (int i = 0; i < n; i++) cst[i][i] = 0;
    while (m--) {
        int a, b, c; fin >> a >> b >> c;
        cst[a][b] = c;
    }
}

//12:45