#include <fstream>
#define inf 20000000
#define dmax 20

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m;
int C[dmax][dmax];
int sol[dmax], solmin[dmax];
int cost, costmin;
bool uz[dmax];

void citire();
void c_h(int);

int main()
{
   citire();
   sol[1]=1;
   c_h(2);
   fout<<costmin;
   return 0;
}

void citire()
{
    int x,y,c,i,j;
    fin>>n>>m;
    for (i=1; i<=m; ++i)
    {
        fin>>x>>y>>c;
        C[x][y]=c;
    }
    for(i=1 ; i<=n; ++i)
       for(j=1; j<=n; j++)
           if(i!=j && !C[i][j])
               C[i][j]=inf;
}


void c_h (int k)
{
    int i;
    if (cost>costmin)
        return;
    if (k==n+1)
    {
        cost=cost+C[sol[n]][1];
        if (cost<costmin && C[1][sol[n]])
        {
            costmin=cost;
            for (i=1; i<=n; ++i)
                solmin[i]=sol[i];
        }
    }

    for (i=2; i<=n; ++i)
        if (!uz[i] && C[i][sol[k-1]])
        {
            uz[i]=1;
            sol[k]=i;
            cost=cost+C[i][sol[k-1]];
            c_h(k+1);
            uz[i]=0;
        }
}