#include <fstream>

#define INF 1000000000

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

long long n , m , x , y , c , cost[25][25] , dp[1000000][25] , sol;

int main() {
    f >> n >> m;

    for(int i = 1 ; i <= m ; ++i) {
        f >> x >> y >> c;
        cost[x][y] = c;
    }

    for(int i = 1 ; i <= (1 << n) ; ++i) {
        for(int j = 1 ; (1 << j) <= i ; ++j) {
            if(((i & (1 << j)) != 0) && ((i & 1) != 0)) {
                long long x = i ^ (1 << j) , cp = i , nrb = 0;

                while(cp) {
                    if(cp % 2 == 1) {
                        ++nrb;
                    }
                    cp /= 2;
                }

                sol = INF;

                for(int k = 0 ; (1 << k) <= x ; ++k) {
                    if((x & (1 << k)) != 0 && cost[k][j] != 0 && (dp[x][k] != 0 || nrb == 2))
                        sol = min(sol , dp[x][k] + cost[k][j]);
                }

                if(sol != INF) {
                    dp[i][j] = sol;
                }
            }
        }
    }

    sol = INF;

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

    if(sol == INF) {
        g << "Nu exista solutie";
    }

    else {
        g << sol;
    }

    return 0;
}