d[1<<15];s[14][14],i,j,u,v,x=-1;main(n){for(scanf("%d%*d",&n);~scanf("%d%d%d",&i,&j,&u)?s[i][j]=u:~x&!!j--<<i?u+=x&1<<j?0:s[j][i],d[v=x^1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,++x<1<<n:1;);i=!printf("%d",d[x-1]);}