#include<cstdio>
#include<vector>
using namespace std;
int n,m,a[1<<18][20];
struct nod
{
    int inf,ct;
};
vector<nod>v[20];
#define nrmare 1000000000
nod makenod(int a,int b)
{
    nod p;
    p.inf=a;
    p.ct=b;
    return p;
}
void citire()
{
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        v[y].push_back(makenod(x,z));
    }
}
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    citire();
    for(int i=1;i<=(1<<n)-1;i++)
        for(int j=0;j<n;j++)
        {
            a[i][j]=nrmare;
        }
    a[1][0]=0;
    for(int i=2;i<(1<<n);i++)
        for(int j=0;j<n;j++)
        {
            if((i&(1<<j))!=0)
            {
                for(int k=0;k<v[j].size();k++)
                {
                    int x=v[j][k].inf,ct=v[j][k].ct;
                    if(i&(1<<x)!=0)
                        if(a[i^(1<<j)][x]+ct<a[i][j])
                            a[i][j]=a[i^(1<<j)][x]+ct;
                }
            }
        }
    int sol=nrmare;
    for(int i=0;i<v[0].size();i++)
    {
        if(a[(1<<n)-1][v[0][i].inf]+v[0][i].ct<sol)
            sol=a[(1<<n)-1][v[0][i].inf]+v[0][i].ct;
    }
    printf("%d",sol);
    return 0;
}