#include<stdio.h>
int n,m,i,j,a[20][20],x,y,c,k,ct,vmin,z[20],viz[20];
void back(int k,int ct,int &vmin,int z[],int n,int viz[])
{
    int i;
    if(k==n+1)
    {
        if(ct+a[z[n]][1]<vmin)
        {
            vmin=ct+a[z[n]][1];
        }
    }
    else
    {
        for(i=1;i<=n;i++)
        {
            if(viz[i]==0 && ct+a[z[k-1]][i]<vmin)
            {
                z[k]=i;
                viz[i]=1;
                back(k+1,ct+a[z[k-1]][i],vmin,z,n,viz);
                viz[i]=0;
            }
        }
    }
}
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            a[i][j]=1000000000;
        }
        a[i][i]=0;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        a[x+1][y+1]=c;
    }
    z[1]=1;
    viz[1]=1;
    vmin=1000000000;
    back(2,0,vmin,z,n,viz);
    printf("%d",vmin);
    return 0;
}