#include <fstream>
#include <vector>
#define MAXN 22
#define INF 2000000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

struct muchie{
    int nod,cost;};

int n,m,x,c[MAXN][270000];
muchie aux;
vector<muchie> GT[MAXN];
bool uz[MAXN][270000];

int pd(short int y,int bin);

int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>aux.nod>>x>>aux.cost;
        GT[x].push_back(aux);}
    x=pd(0,(1<<n)-1);
    if(x==INF)
        g<<"Nu exista solutie\n";
    else
        g<<x<<'\n';
    f.close();
    g.close();
    return 0;
}

int pd(short int y,int bin){
    int mn=INF,i;
    if(!bin)
        return 0;
    if(uz[y][bin])
        return c[y][bin];
    for(i=0;i<GT[y].size();i++){
        x=(bin xor (1<<(GT[y][i].nod)));
        if(x>bin&&!(bin==(1<<y)&&!GT[y][i].nod))
            continue;
        x=pd(GT[y][i].nod,bin xor (1<<y));
        if(x+GT[y][i].cost<mn)
            mn=x+GT[y][i].cost;}
    c[y][bin]=mn;
    uz[y][bin]=1;
    return mn;}