#include <stdio.h>

const int nmax=18;
const int INF=0x3F3F3F3F;

int cost[nmax][nmax];
int aux[1 << nmax][nmax];///multime, nod terminal
int n;

int calc(int lnt, int nod)
{
    int c,i,val;

    if (aux[lnt][nod])
        return aux[lnt][nod];///daca am mai calculat acest rezultat atunci il returnez
    c=INF;///costul curent este infinit
    if (lnt == (1 << n) - 1)///daca toate nodurile fac parte din lant
    {
        if (cost[nod][0])
            c=cost[nod][0];///returnez costul ultimului nod din ciclu pentru a-l aduna la costul lantului
    }
    else
    {
        for (i=0; i < n; i++)///iau toate nodurile
            if (cost[nod][i] && !((lnt >> i) & 1))///daca sunt vecine cu nodul curent (nod) si nu fac parte din lant(lnt)
            {
                val=cost[nod][i]+calc(lnt | (1 << i),i);///cost+costul pentru restul lantului
                if (val < c)
                    c=val;
            }
    }
    aux[lnt][nod]=c;
    return c;
}

int main()
{
    FILE *f;
    int m,x,y,c,i,ans;

    f=fopen("hamilton.in","r");
    fscanf(f,"%d%d",&n,&m);
    for (i=1; i<=m; i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&c);
        cost[x][y]=c;
    }
    fclose(f);

    ans=calc(1,0);

    f=fopen("hamilton.out","w");
    if (ans == INF)
        fprintf(f,"Nu exista solutie");
    else
        fprintf(f,"%d",ans);
    fclose(f);
}