#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
struct vecin{
    int dest;
    int cost;
};
vector<vecin> vecini[19];
int dp[int(1 << 18) + 5][19];
int main(){
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++){
        int a, b, c;
        fin >> a >> b >> c;
        vecini[a].push_back({b, c});
    }
    for (int config = 0; config < (1 << n); config++){
        for (int last = 0; last < n; last++)
            dp[config][last] = 2e9;
    }
    dp[1][0] = 0;
    for (int config = 1; config < (1 << n); config++){
        for (int last = 0; last <= n - 1; last++){
            int config_last = (1 << last);
            if ((config & config_last) != 0){
                for (vecin vec: vecini[last]){
                    int config_nod = (1 << vec.dest);
                    if ((config & config_nod) == 0){
                        dp[config | config_nod][vec.dest] = min(dp[config | config_nod][vec.dest],
                                                                dp[config][last] + vec.cost);
                    }
                }
            }
        }
    }
    int min_ans = 2e9;
    for (int last = 1; last <= n; last++){
        for (vecin vec: vecini[last]){
            if (vec.dest == 0){
                min_ans = min(min_ans, dp[(1 << n) - 1][last] + vec.cost);
            }
        }
    }
    if (min_ans != 2e9)
        fout << min_ans;
    else
        fout << "Nu exista solutie";
    return 0;
}