#include <iostream>
#include <fstream>
#include <unordered_set>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int NMAX = 20;
const int INFI = 0x3f3f3f3f;
int mc[NMAX][NMAX];
int dp[NMAX][1 << NMAX];
int cost_optim = INFI;
int N, M;
unordered_set < int > us;

void read(){
    fin >> N >> M;
    for(int i = 0; i < M; i++){
        int x, y, c;
        fin >> x >> y >> c;
        mc[x][y] = c;
    }
}

void hamilton_with_set_rec(int nod, int cost_curent){
    if(us.size() == 0 && mc[nod][0]){
        if(cost_optim > cost_curent + mc[nod][0]){
            cost_optim = cost_curent + mc[nod][0];
        }
        return;
    }

    unordered_set < int > temp_set;
    for(int el: us){
        temp_set.insert(el);
    }

    for(int el: temp_set){
        if(mc[nod][el] != 0){
            us.erase(el);
            hamilton_with_set_rec(el, cost_curent + mc[nod][el]);
            us.insert(el);
        }
    }
}

void hamilton_with_set(){
    for(int i = 1; i < N; i++){
        us.insert(i);
    }
    hamilton_with_set_rec(0, 0);

    if(cost_optim != INFI){
        fout << cost_optim;
    }else{
        fout << "Nu exista solutie";
    }
}

void hamilton_top_down_no_memo(int nod, int config, int cost_curent){
    if(config == 0 && mc[nod][0]){
        if(cost_optim > cost_curent + mc[nod][0]){
            cost_optim = cost_curent + mc[nod][0];
        }
        return;
    }

    /// mica optimizare
    if(cost_curent > cost_optim){
        return;
    }

    for(int i = 0; i < N; i++){
        /// nodul i inca trebuie vizitat si exista muchie intre nodul nod si i
        if(((1 << i) & config) && mc[nod][i]) {
            /// updatam configuratia excluzand nodul i
            int new_config = config ^ (1 << i);
            hamilton_top_down_no_memo(i, new_config, cost_curent + mc[nod][i]);
        }
    }
}

int hamilton_top_down_memo(int nod, int config){
    if(config == 0){
        if(mc[nod][0]){
            return mc[nod][0];
        }
        return INFI;
    }

    if(dp[nod][config] != 0){
        return dp[nod][config];
    }

    int min_cost = INFI;
    for(int i = 0; i < N; i++){
        /// nodul i inca trebuie vizitat si exista muchie intre nodul nod si i
        if(((1 << i) & config) && mc[nod][i]) {
            int new_config = config ^ (1 << i);
            int new_cost = mc[nod][i] + hamilton_top_down_memo(i, new_config);
            min_cost = min(new_cost, min_cost);
        }
    }

    return (dp[nod][config] = min_cost);
}

void hamilton_with_bits_top_down(){
    int config = (1 << N) - 1 - 1;
    /// (1 << N) - 1 => 1111...1 => de n ori, iar apoi mai scad un 1 - pentru a elimina bitul asociat nodului de inceput 0
    /// hamilton_top_down_no_memo(0, config, 0);
    ///hamilton_top_down_memo(0, config, 0);
    int result = hamilton_top_down_memo(0, config);
    if(result != INFI){
        fout << result;
    }else{
        fout << "Nu exista solutie";
    }
}

int main()
{
    read();
    /// hamilton_with_set();
    hamilton_with_bits_top_down();
    return 0;
}