#include <iostream>
#include <fstream>
#include <stdint.h>
#include <vector>

int32_t min(int32_t x, int32_t y) {
    return (x < y) ? x : y;
}

const int32_t MAX_VAL = 1000000000;
const int32_t MAX_N = 18;
const int32_t MAX_N_POW_2 = 1 << (MAX_N - 1);

int32_t adj[MAX_N][MAX_N];
int32_t dp[MAX_N_POW_2][MAX_N];
int main() {
    std::ifstream fin("hamilton.in");
    std::ofstream fout("hamilton.out");

    int32_t n, m;
    fin >> n >> m;

    for(int32_t i = 0; i != m; ++i) {
        int32_t x, y, c;
        fin >> x >> y >> c;
        adj[x][y] = c;
    }

    int32_t nPow2 = 1 << (n - 1);
    for(int32_t i = 0; i != nPow2; ++i)
        for(int32_t j = 0; j != n; ++j)
            dp[i][j] = MAX_VAL;
    dp[0][0] = 0;
    for(int32_t i = 1; i != n; ++i) {
        if(adj[0][i])
            dp[1 << (i - 1)][i] = adj[0][i];
    }

    for(int32_t i = 1; i != nPow2; ++i) {
        for(int32_t j = 1; j != n; ++j) {
            if(!(i & (1 << (j - 1))))
                continue;
            for(int32_t k = 1; k != n; ++k) {
                if(!(i & (1 << (k - 1))))
                    continue;
                if(!adj[k][j])
                    continue;
                dp[i][j] = min(dp[i][j], dp[i ^ (1 << (j - 1))][k] + adj[k][j]);
            }
        }
    }

    --nPow2;
    int32_t minCost = MAX_VAL;
    for(int32_t i = 1; i != n; ++i) {
        if(adj[i][0])
            minCost = min(minCost, dp[nPow2][i] + adj[i][0]);
    }

    if(minCost == MAX_VAL) {
        fout << "Nu exista solutie";
    } else {
        fout << minCost;
    }

    fin.close();
    fout.close();

    return 0;
}