#include <fstream>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
void bkt(int k);
int mat[20][20],t[20],us[20],lg,lgmin=9999999,n;
int main()
{
    int m,i,j,a,b,c;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                mat[i][j]=-1;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        mat[a][b]=c;
        //mat[b][a]=c;
    }
    t[1]=0;
    bkt(2);
    fout<<lgmin;
    return 0;
}

void bkt(int k)
{
    int i;
    if(k==n+1 && mat[t[n]][0]>0)
        {if(lg+mat[t[n]][0]<lgmin) lgmin=lg+mat[t[n]][0];}
    else{
        for(i=1;i<n;i++)
            if(mat[t[k-1]][i]>0 && !us[i])
                {
                  t[k]=i;
                  us[i]=1;
                  lg+=mat[t[k-1]][i];

                  bkt(k+1);

                  us[i]=0;
                  lg-=mat[t[k-1]][i];
                }
    }
}