#include <bits/stdc++.h>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int lim = 1<<18;

int gr[20][20];
int dp[lim+10][20];
vector<int> masti[20];
int main(){
    int n, m;
    f >> n >> m;

    for(int i = 0; i < m; ++i){
        int a, b, c;
        f >> a >> b >> c;
        gr[a][b] = c;
    }

    for(int mask = 0; mask < (1<<n); ++mask){
        masti[__builtin_popcount(mask)].push_back(mask);
    }

    for(int i = 0; i <= n; ++i){
        for(auto x : masti[i]){
            for(int nod = 0; nod < n; ++nod){
                if(dp[x][nod] || (x == 1 && nod == 0)){
                    for(int bit = 0; bit < n; ++bit){
                        if(x&(1<<bit)) continue;
                        if(gr[nod][bit] == 0) continue;
                        if(dp[x|(1<<bit)][bit] == 0) dp[x|(1<<bit)][bit] = dp[x][nod] + gr[nod][bit];
                        else{
                            dp[x|(1<<bit)][bit] = min(dp[x|(1<<bit)][bit], dp[x][nod] + gr[nod][bit]);
                        }
                    }
                }
            }
        }
    }
    int best = 2e9;
    for(int nod = 0; nod < n; ++nod){
        if(dp[(1<<n)-1][nod] && gr[nod][0]){
            best = min(best, dp[(1<<n)-1][nod] + gr[nod][0]);
        }
    }

    if(best == 2e9) g << "Nu exista solutie";
    else g << best;
    return 0;
}