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

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

const int full = (1<<18);

int dp[18][full] , n , m , x , y , c , cost[18][18];

// dp[i][j] = costul minim al unui lant care se termina cu i si are in el toate nodurile setate

// cu unu in conf binara a lui j ( si incepe cu 1 )

vector <int> g[19];

int main(){

    cin >> n >> m;

    while(m--){

        cin >> x >> y >> c;

        cost[x][y] = c;

        g[x].push_back(y);
    }

    int f = (1<<n)-1;

    for(int i = 0; i < n ; i++){

        for(int j = 0 ; j <= f ; j++){

            dp[i][j] = 1e9;
        }
    }

    dp[0][1] = 0;

    for(int j = 1 ; j <= f ; j++){

        for(int i = 0 ; i < n ; i++){

            if(dp[i][j] == 1e9) continue;

            for(auto it : g[i]){

                if(!(j&(1<<it)))dp[it][(j|(1<<it))]=min(dp[it][(j|(1<<it))],dp[i][j] + cost[i][it]);
            }
        }
    }

    int ans = 1e9;

    for(int i = 1 ; i < n ; i++){

        if(cost[i][0]) ans = min(ans,dp[i][f] + cost[i][0]);
    }

    if(ans == 1e9) cout << "Nu exista solutie";
    else cout << ans;

    return 0;
}