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