#include <bits/stdc++.h>

using namespace std;

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

const int inf = 1e9;
int n, m, cost[20][20], dp[(1 << 19)][19];
vector <int> G[20];

int main(){
    fin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int x, y;
        fin >> x >> y;
        fin >> cost[x][y];
        G[x].push_back(y);
    }
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < (1 << n); ++j){
            dp[j][i] = inf;
        }
    }
    dp[1][0] = 0;
    for (int i = 1; i < (1 << n); ++i){
        for (int j = 0; j < n; ++j){
            if (dp[i][j] != inf){
                for (auto it : G[j]){
                    if (((i >> it) & 1) == 0){
                        dp[(i | (1 << it))][it] = min(dp[(i | (1 << it))][it], dp[i][j] + cost[j][it]);
                    }
                }
            }
        }
    }
    int minim = 1e9;
    int mask = (1 << n) - 1;
    for (int i = 1; i < n; ++i){
        if (dp[mask][i] != inf && cost[i][0] > 0){
            minim = min(minim, dp[mask][i] + cost[i][0]);
        }
    }
    if (minim == 1e9){
        fout << "Nu exista solutie";
    }
    else{
        fout << minim;
    }
    fin.close();
    fout.close();
    return 0;
}