#include<stdio.h>
#include<stdlib.h>
#define INF 1000000000
long c[19][262145][19]={0},cost[19][19]={0},deg[19]={0},*g[19],n,m,i,j,a[308],b[308],d,k,l,t,u[19],r,p,min;
int main()
{freopen("hamilton.in","r",stdin);
freopen("hamilton.out","w",stdout);
scanf("%ld%ld",&n,&m);
for(i=1;i<=m;i++)
       {scanf("%ld%ld%ld",&a[i],&b[i],&d);
       cost[a[i]][b[i]]=d;
       deg[a[i]]++;}
for(i=0;i<n;deg[i++]=0)
       g[i]=(long*)malloc(deg[i]*sizeof(long));
for(j=1;j<=m;j++)
       g[a[j]][deg[a[j]]++]=b[j];
for(i=0;i<n;i++)
for(j=0;j<(1<<n);j++)
if(j==(1<<i))
       c[i][j][i]=0;
else
       c[i][j][i]=INF;
for(i=0;i<n;i++)
for(j=0;j<(1<<n);j++)
       {for(l=0,t=0,k=j;k;k>>=1,l++)
       if(k&1)
              u[t++]=l;
       for(r=0;r<t;r++)
       if(u[r]!=i)
              {min=INF;
              for(p=0;p<t;p++)
              if(cost[u[p]][u[r]]&&min>cost[u[p]][u[r]]+c[i][j^(1<<u[r])][u[p]])
                      min=cost[u[p]][u[r]]+c[i][j^(1<<u[r])][u[p]];
              c[i][j][u[r]]=min;}}
min=c[g[0][0]][(1<<n)-1][0]+cost[0][g[0][0]];
for(i=0;i<n;i++)
for(j=0;j<deg[i];j++)
if(min>c[g[i][j]][(1<<n)-1][i]+cost[i][g[i][j]])
      min=c[g[i][j]][(1<<n)-1][i]+cost[i][g[i][j]];
if(min==INF)
      printf("-1");
else
      printf("%ld",min);
fclose(stdin);
fclose(stdout);
return 0;}