#include<cstdio>
#include<vector>
#define inf 2000000000
using namespace std;
int c[19][19],d[262144][19];
vector<int> l[19];





int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    int n,i,j,m,lim,p,u,v,s=inf;
    vector<int>::iterator it;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&u,&v);
        scanf("%d",&c[u][v]);
        l[v].push_back(u);
    }
    lim=(1<<n)-1;
    for(i=0;i<=lim;++i)
        for(j=0;j<n;++j)
            d[i][j]=inf;
    d[1][0]=0;
    for(i=1;i<=lim;i+=2)
        for(j=0;j<n;++j)
            if((i&(1<<j))!=0)
                for(it=l[j].begin();it!=l[j].end();++it)
                {
                    p=*it;
                    if(d[i^(1<<j)][p]+c[p][j]<d[i][j])
                        d[i][j]=d[i^(1<<j)][p]+c[p][j];
                }
    /*for(i=0;i<=lim;++i)
    {
        for(j=0;j<n;++j)
            printf("%d ",d[i][j]);
        printf("\n");
    }*/
    for(it=l[0].begin();it!=l[0].end();++it)
        s=min(s,d[lim][*it]+c[*it][0]);
    printf("%d\n",s);
    return 0;
}