#include <fstream>
#include <vector>

using namespace std;

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

const int NMAX = 18;
const int inf = 1e9;
const int VMAX = (1 << NMAX);

long long dp[VMAX + 1][NMAX + 5];
int cost[NMAX + 5][NMAX + 5];
vector <int> g[NMAX + 5];

int main(){

    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n = 0, m = 0;
    cin >> n >> m;


    for(int i = 0; i <= n; i++)
        for(int j = 0; j < n; j++)
            cost[i][j] = inf;

    for(int i = 0; i < (1 << n); i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = inf;

    for(int i = 0; i < m; i++){

        int x = 0, y = 0, c = 0;
        cin >> x >> y >> c;

        cost[x][y] = c;
        g[y].push_back(x);

    }

    /*

        dp[mask][i] = costul minim al unui ciclu ce contine varfurile (bitii setati) din masca si se termina in varful i, incepand din varful 0
        dp[mask][j] = min(dp[mask ^ (1 << j)][j]) + cost(j, i);

    */

    dp[1][0] = 0;
    for(int mask = 3; mask < (1 << n); mask += 2){
        for(int i = 1; i < n; i++){

            if((mask & (1 << i)) == 0)
                continue;

            int new_mask = (mask ^ (1 << i));

            for(auto j : g[i])
                dp[mask][i] = min(dp[mask][i], dp[new_mask][j] + 1LL * cost[j][i]);

        }
    }


    long long ans = 1e9;
    for(int i = 1; i < n; i++)
        ans = min(ans, dp[(1 << n) - 1][i] + cost[i][0]);

    if(ans != inf)
        cout << ans;
    else cout << "Nu exista solutie";

    return 0;
}