/// patratele
#include <bits/stdc++.h>
using namespace std;

#define MOD 666013

ifstream fin("patratele.in");
ofstream fout("patratele.out");

long long i, n, m, mat[20][20], j, y, x, c, vf, q[20], dp[1 << 18][20];

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fin >> n >> m;
  n--;
  for (i = 1; i <= m; i++)
  {
    fin >> x >> y >> c;
    mat[x][y] = c;
  }
  for (i = 1; i <= (1 << (n + 1)) - 1; i++)
  {
    vf = 0;
    for (j = 0; j <= n; j++)
      dp[i][j] = LLONG_MAX;
    for (j = 0; j <= n; j++)
      if (i & (1 << j))
        q[vf++] = j;
    if (vf == 1)
      dp[i][q[0]] = 0;
    else
    {
      for (j = 0; j < vf; j++)
        for (y = j + 1; y < vf; y++)
        {
          if (mat[q[j]][q[y]] && dp[i ^ (1 << q[y])][q[j]] != LLONG_MAX)
            dp[i][q[y]] = min(dp[i ^ (1 << q[y])][q[j]] + mat[q[j]][q[y]], dp[i][q[y]]);
          if (mat[q[y]][q[j]] && dp[i ^ (1 << q[j])][q[y]] != LLONG_MAX)
            dp[i][q[j]] = min(dp[i ^ (1 << q[j])][q[y]] + mat[q[y]][q[j]], dp[i][q[j]]);
        }
    }
  }
  long long ras = LLONG_MAX;
  for (i = 0; i <= n; i++)
    ras = min(ras, dp[(1 << (n + 1)) - 1][i]);
  fout << ras;

  return 0;
}