#include <iostream>
#include <fstream>
#include <cstring>
#define DIM 20
#define DMAX 1 << 18
#define oo (1 << 30) - 1

using namespace std;

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

int N,M, C[DMAX][DIM];

struct node{
    int vf, c;
    node *next;
}*L[DIM];

void add(int x, int y, int c){
    node *p = new node;
    p->vf = x, p->c = c;
    p->next = L[y];
    L[y] = p;
}

void read(int &N){
    f>>N>>M;
    int x,y,c;
    for(int i=1; i<=M; i++){
        f>>x>>y>>c;
        add(x,y,c);
    }
}

int solve(int mid, int last){
    if(C[mid][last] == -1){
        C[mid][last] = oo;
        for(node *p = L[last]; p != nullptr; p = p->next)// parcurg nodurile care arata spre ultimul nod din lant
            if(mid & (1 << p->vf)){// le aleg doar pe cele care apartin lantului
                if(p->vf == 0 &&  (mid ^ (1 << last)) != 1) // nodul 1 trebuie sa il scot ultimul
                    continue;
                C[mid][last] = min(C[mid][last], solve( mid ^ (1 << last), p->vf) + p->c);
            }
    }
    return C[mid][last];
}

int main()
{
    read(N);
    memset(C, -1, sizeof(C));
    C[1][0] = 0;
    int sol = oo;
    for(node *p = L[0]; p != nullptr; p = p->next)
        sol = min(sol, solve((1<<N) - 1, p->vf) + p->c);
    if(sol == oo) g<<"Nu exista solutie";
    else g<<sol;
}