#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
#define INF 1000000000

int adi[18][18];
int dp[18][(1 << 17)]; //dp[nod][conf] = costul minim ca sa se ajunga in nodul nod trecand exact prin
//nodurile cu 1 din conf
int N, M;

int main() {
    fin >> N >> M;
    int a, b, c;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            adi[i][j] = INF;
        }
    }
    for(int i = 1; i <= M; i++) {
        fin >> a >> b >> c;
        adi[a][b] = c;
    }

    for(int conf = 1; conf < (1 << (N - 1)); conf++) {
        for(int i = 0; i < N; i++) {
            dp[i][conf] = INF;
        }
    }
    for(int i = 0; i < N - 1; i++) {
        dp[i][(1 << (i))] = adi[N - 1][i];
        //cout << dp[i][(1 << (i))] << "\n";
    }
    dp[N - 1][0] = 0;
    for(int conf = 1; conf < (1 << (N - 1)); conf++) {
        for(int nodnou = 0; nodnou < N - 1; nodnou++) {
            if((conf & (1 << (nodnou))) == 0) {
                for(int nodvechi = 0; nodvechi < N - 1; nodvechi++) {
                    if((conf & (1 << (nodvechi))) != 0 && adi[nodvechi][nodnou] < INF) {
                        dp[nodnou][conf ^ (1 << (nodnou))] = min(dp[nodnou][conf ^ (1 << (nodnou))], dp[nodvechi][conf] + adi[nodvechi][nodnou]);
                        //cout << dp[nodnou][conf ^ (1 << (nodnou))] << "\n";
                        //cout << "Ma pot duce din " << nodvechi << " in " << nodnou << "\n";
                    }
                }
            }
        }
    }
    int rez = INF;
    for(int i = 0; i < N - 1; i++) {
        if(adi[i][N - 1] < INF) {
            rez = min(rez, dp[i][(1 << (N - 1)) - 1] + adi[i][N - 1]);
        }
        
    }
    if(rez == INF) {
        fout << "Nu exista solutie";
    }
    else {
        fout << rez;
    }
    return 0;
}