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

ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int oo = 0x3f3f3f3f;

int n, T, d[18][18];
vector<vector<int>> dp;

void read();

int main()
{
    read();
    dp[0][1] = 0;
    for (int i = 1; i < n; i++)
        dp[i][(1<<i)] = (d[0][i] ? d[0][i] : oo);
    for (int mask = 1; mask < T; mask++){
        vector<int> From, To;
        for (int i = 0; i < n; i++)
            ((mask & (1<<i)) ? From.pb(i) : To.pb(i));
        for (auto from : From){
            for (auto to: To){
                if (!d[from][to]) continue;
                int nmsk = (mask|(1<<to));
                if (dp[to][nmsk] > d[from][to] + dp[from][mask])
                    dp[to][nmsk] = dp[from][mask] + d[from][to];
            }
        }
    }
    
    if (dp[0][T] == oo) g << "Nu exista solutie";
    else g << dp[0][T];
    
    return 0;
}

void read()
{
    int m;
    f >> n >> m;
    while (m--){
        int x, y, z; f >> x >> y >> z;
        d[x][y] = z;
    }
    T = (1<<n) - 1;
    dp.resize(n, vector<int>(T+1, oo));
}

/*

*/