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