#include <cstdio>
#include <vector>

#define NMAX 18
#define INF 0x3f3f3f3f

using namespace std;

vector <int>v[NMAX];

int n,m,x,y,c,boss=INF;
int cost[NMAX][NMAX],best[1<<NMAX][NMAX];

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++)
     {
         scanf("%d %d",&x,&y);
         v[y].push_back(x);
         scanf("%d",&cost[x][y]);
     }
    for (int i=1;i<(1<<n);i++)
      for (int j=0;j<n;j++)
         if (i!=(1<<j))best[i][j]=INF;

    for (int i=1;i<(1<<n);i++)
       for (int j=0;j<n;j++)
         if (i&(1<<j))
           for (auto k:v[j])
             if (i&(1<<k))
               best[i][j]=best[i][j]<best[i^(1<<j)][k]+cost[k][j]?best[i][j]:best[i^(1<<j)][k]+cost[k][j];

    for (auto k:v[0])
       if (boss>best[(1<<n)-1][k]+cost[k][0])
         boss=best[(1<<n)-1][k]+cost[k][0];
    printf("%d",boss);

    fclose(stdin);
    fclose(stdout);
}