using namespace std;
#include<iostream>
#include<fstream>
#include<vector>

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

#define NMAX 20
#define INF 1e9

int n, m;
int dp[1<<18][NMAX], mat[NMAX][NMAX];

int main() {
    
    fin >> n >> m;
    for (int i = 1; i<=m; i++) {
        int a,b,c;
        fin >> a >> b >> c;
        mat[a][b] = c;
    }
    
    dp[1][0] = 1;
    for (int conf = 2; conf<(1<<n); conf++) {
        
        int pow2 = 1, cnt = 0;
        while (pow2 <= conf) {
            if (conf & pow2) { ///daca adauga un nod
                int mask = conf ^ pow2; ///configuratia cu nodul in plus
                if (mask) { 
                    dp[conf][cnt] = INF;
                    for (int nod = 0; nod<n; nod++) {
                        if (mat[nod][cnt] && dp[mask][nod]) {
                            dp[conf][cnt] = min(dp[conf][cnt], dp[mask][nod] + mat[nod][cnt]);
                        }
                    }
                }                
            }
            
            pow2 *= 2;
            cnt++;
        }
    }
    
    int ans = INF;
    for (int i = 0; i<n; i++) {
        if (dp[(1<<n)-1][i] && mat[i][0]) {
            ans = min(ans, dp[(1<<n)-1][i] + mat[i][0]);
        }
    }
    
    if (ans != INF) {
        fout << ans-1;
    } else {
        fout << "Nu exista solutie!";
    }
    
    
    return 0;
}