#include <bits/stdc++.h>
#define mxint 2000000000

int ham[131072][18];

int leg0[18];

std::vector< std::pair<int,int> > nd[18];

int main()
{
    int n,m,i,a,b,c,j,q,k,nod,pz,val,mn=mxint;
    FILE*fi,*fo;
    fi=fopen("hamilton.in","r");
    fo=fopen("hamilton.out","w");
    fscanf(fi,"%d%d",&n,&m);
    for(i=0; i<m; i++)
    {
        fscanf(fi,"%d%d%d",&a,&b,&c);
        nd[a].push_back({b,c});
        if(a==0)
        {
            ham[1<<(b-1)][b]=c;
        }
        if(b==0)
            leg0[a]=c;
    }
    for(i=0; i<1<<(n-1); i++)
        for(j=1; j<18; j++)
        {
            if((i&(1<<(j-1)))!=0 && ham[i][j]!=0)
            {
                for(k=0; k<nd[j].size(); k++)
                {
                    nod=nd[j][k].first;
                    if((i & (1<<(nod-1)))==0)
                    {
                        pz=i | (1<<(nod-1));
                        val=nd[j][k].second+ham[i][j];
                        if(ham[pz][nod]==0 || ham[pz][nod]>val)
                        {
                            ham[pz][nod]=val;
                        }
                    }
                }
            }
        }
    q=(1<<(n-1))-1;
    for(i=1; i<n; i++)
    {
        if(leg0[i]!=0 && ham[q][i]!=0 && leg0[i]+ham[q][i]<mn)
        {
            mn=leg0[i]+ham[q][i];
        }
    }
    if(mn!=mxint)
    fprintf(fo,"%d",mn);
    else fprintf(fo,"Nu exista solutie");
    fclose(fi);
    fclose(fo);
    return 0;
}