#include<cstdio>
#include<vector>
using namespace std;
int re[20][1<<18],bm,p2[18],mu[20][20],n;
const int NMA=20000000;
int calc(int p,int bm)
{
    bm=bm-p2[p];
    if(re[p][bm]!=0)
    return re[p][bm];
    int an;
    if(p!=0 || bm!=0)
    an=NMA;
    else
    {
    an=1;
    }
    int i;
    for(i=n-1;i>=0;i--)
    if((bm & p2[i]) && mu[i][p]>0)
    {
        an=min(an,calc(i,bm)+mu[i][p]);
    }
    re[p][bm]=an;
    return an;
}
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    int m,i,j,no,co,an;
    an=NMA;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&j,&no,&co);
        mu[j][no]=co;
    }
    p2[0]=1;
    for(i=1;i<=17;i++)
    p2[i]=p2[i-1]*2;
    bm=(1<<n)-1;
    for(i=1;i<n;i++)
    if(mu[i][0]!=0)
    calc(i,bm);
    for(i=1;i<n;i++)
    if(mu[i][0]!=0 && re[i][bm-p2[i]])
    {
    an=min(an,mu[i][0]+re[i][bm-p2[i]]);
    }
    if(an<NMA)
    printf("%d\n",an-1);
    else
    printf("Nu exista solutie\n");
    return 0;
}