#include <iostream>
#include <fstream>
using namespace std;
int m[20][20],rez[270000][20],n,nm,i,x,y,c,i1,mn,ax;
int f1(int ca,int fin)
{
    int i;
    if (((1<<fin)^ca)==1)
        {
            if (m[0][fin]!=999999999)
            {
                rez[ca][fin]=m[0][fin];
            }
            else
                rez[ca][fin]=999999998;
            return 0;
        }
    for (i=1;i<n;i++)
        {
            if ((m[i][fin]!=999999999)&&(((1<<i)&ca)!=0))
            {
                if (rez[ca^(1<<fin)][i]==999999999)
                    {
                        f1(ca^(1<<fin),i);
                    }
                rez[ca][fin]=min(rez[ca][fin],rez[ca^(1<<fin)][i]+m[i][fin]);
            }
        }
    return 0;
}
int main(void)
{
    FILE * f;
    f=fopen("hamilton.in","r");
    ofstream g("hamilton.out");
    fscanf(f,"%d%d",&n,&nm);
    for (i=0;i<20;i++)
        for (i1=0;i1<20;i1++)
            m[i][i1]=999999999;
    for (i=1;i<=nm;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&c);
        m[x][y]=c;
    }
    for (i=0;i<270000;i++)
        for (i1=0;i1<20;i1++)
            rez[i][i1]=999999999;
    for (i=0;i<n;i++)
        rez[1<<i][i]=0;
    mn=999999999;
    ax=(1<<n)-1;
    for (i=1;i<n;i++)
    {
        f1(ax,i);
        mn=min(rez[ax][i]+m[i][0],mn);
    }
    if (mn!=999999999)
        g<<mn;
    else
        g<<"Nu exista solutie";
    g.close();
    return 0;
}