#include <fstream>
#include <limits>

std::ifstream in("hamilton.in");
std::ofstream out("hamilton.out");

constexpr int N = 18;
constexpr int LIM = 1 << N;
constexpr int INF = 1e9;
//int n, m;
//int dp[LIM][N]; // costul minim al unui drum elementar care incepe in 0, contine toate varfurile din submultimea 
                     // codificata de i(in binar), si se termina pe varful j(care apartine multimii reprezentate de i)
//int cost[N][N];

int main (){
    int n, m;
    in >> n >> m;
    int lim = 1 << n;
    int *dp = new int[lim * (n+1)];
    int *cost = new int[n*(n+1)];
    std::fill(cost, cost + n*(n+1), INF);
    //for(int i=0; i<n; ++i){
    //    std::fill(cost[i], cost[i] + n, INF);
    //    cost[i][i] = 0;
    //}
    for(int i=0; i<m; ++i){
        int u, v, c;
        in >> u >> v >> c;
        cost[u*n + v] = c;
    }
    std::fill(dp, dp + lim * (n+1), INF);
    //for(int i=0; i<lim; ++i)
    //   std::fill(dp[i], dp[i] + n, INF);
    dp[1*n + 0] = 0;
    for(int mask=1; mask<lim; mask += 2){
        for(int node=0; node<n; ++node){
            if ((1 << node) & mask){///j apartine i, deci are sens dp[i][j]
                for (int succ=0; succ<n; succ++){
                    if (!((1 << succ) & mask) && cost[node * n + succ] != INF && succ != node){///k e un succesor al lui j
                        int newMask = (mask | (1 << succ));
                        dp[newMask*n + succ] = std::min(dp[newMask*n + succ], dp[mask*n + node] + cost[node*n + succ]);
                    }
                }
            }
        }
    }
    int mask = (1 << n) - 1;
    int res=INF;
    for(int j=1; j<n; ++j){
        if(cost[j*n + 0] == INF) continue;
        res = std::min(res, dp[mask*n + j] + cost[j*n + 0]);
    }
    if(res == INF){
        out << "Nu exista solutie";
    }
    else out << res;
}