/*
                         __
                   _.--""  |
    .----.     _.-'   |/\| |.--.
    |    |__.-'   _________|  |_)  _______________
    |  .-""-.""""" ___,    `----'"))   __   .-""-.""""--._
    '-' ,--. `    |Cezar| .---.       |:.| ' ,--. `      _`.
     ( (    ) ) __|  7  |__\\|// _..-- \/ ( (    ) )--._".-.
      . `--' ;\__________________..--------. `--' ;--------'
       `-..-'                               `-..-'
 */
#include <iostream>
#include <fstream>

using namespace std;

const int N = 18;
const int INF = (1<<30)-1;
int cost[N][N];
int dp[1<<N][N];

int solve(int n){
    dp[1][0] = 0;
    for(int mask = 0;mask<(1<<n); mask++){
        for(int i = 0; i < n; i++){
            if((mask & (1<<i)) ) {
                for (int j = 0; j < n; j++) {
                    if(!(mask & (1<<j)) && cost[i][j] != INF){
                        int new_mask = mask | (1<<j);
                        dp[new_mask][j] = min(dp[new_mask][j],dp[mask][i] + cost[i][j]);
                    }
                }
            }
        }
    }
    int ans = INF;
    for(int i=0;i<n;i++){
        if(cost[i][0] != INF){
           ans = min(ans,dp[(1<<n)-1][i] + cost[i][0]);
        }
    }
    if(ans == INF)
        ans = -1;
    return ans;
}

void init(int n){
    for(int i = 0 ;i<n;i++){
        for(int j=0;j<n;j++) {
            cost[i][j] = INF * (i!=j);
        }
        for(int j = 0;j<(1<<n);j++)
            dp[j][i] = INF;
    }
}

int main() {
    ifstream in("hamilton.in");
    ofstream out("hamilton.out");
    int n,m;
    in>>n>>m;
    init(n+1);
    for(int i=0;i<m;i++){
        int x,y;
        in>>x>>y;
        in>>cost[x][y];
    }
    int ans = solve(n);
    if(ans == -1)
        out<<"Nu exista solutie";
    else out<<ans;
    return 0;
}