#include <fstream>
#include <climits>

using namespace std;

int n, m, i, j, sol = INT_MAX;
int cost[20][20], dp[20][(1 << 20)];
// cost[i][j] = costul muchiei i -> j
// dp[i][mask] = drumul de cost minim de la 0 la i cu mask

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin >> n >> m;
    while(m--){
        fin >> i >> j >> cost[i][j];
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < (1 << n); j++){
            dp[i][j] = INT_MAX;
        }
    }
    dp[0][1] = 0;
    
    for(int mask = 1; mask < (1 << 20); mask++){
        for(int i = 0; i < n; i++){
            if(dp[i][mask] == INT_MAX){
                continue;
            }
            for(int vec = 0; vec < n; vec++){
                if(!((1 << vec) & mask) && cost[i][vec]){
                    dp[vec][mask + (1 << vec)] = min(dp[vec][mask + (1 << vec)], 
                                                    dp[i][mask] + cost[i][vec]);
                }
            }
        }
    }

    for(int i = 1; i < n; i++){
        if(cost[i][0]){
            sol = min(sol, dp[i][(1 << n) - 1] + cost[i][0]);
        }
    }

    if(sol == INT_MAX){
        fout << "Nu exista solutie";
    }
    else{
        fout << sol;
    }

    return 0;
}