#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 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;
    }

    /** stergem si adaugam intr-o structura de date pe care o modificam -> EROARE
    for(int el: us){
        if(mc[nod][el] != 0){
            us.erase(el);
            hamilton_with_set_rec(nod, cost_curent + mc[nod][el]);
            us.insert(el);
        }
    }*/

    /// new set in order to avoid the issue from above
    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";
    }
}

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