#include <fstream>
#include <climits>

using namespace std;

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

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin >> n >> m;
    if(n == 1){
        fout << 0;
        return 0;
    }
    while(m--){
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
    }
    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 << n); mask++){
        for(int i = 0; i < n; i++){
            if(dp[i][mask] == INT_MAX){
                continue;
            }
            for(int vec = 0; vec < n; vec++){
                if(!(mask & (1 << vec)) && cost[i][vec]){
                    dp[vec][mask+(1 << vec)] = min(dp[vec][mask+(1 << vec)],
                                                    dp[i][mask] + cost[i][vec]);
                }
            }
        }
    }

    for(int i = 0; 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;
}