#include <bits/stdc++.h>
using namespace std;
const int nmax = 1000;
int d[nmax][20], cost[20][20];

int main(){
  ifstream fin("hamilton.in");
  ofstream fout("hamilton.out");
  int n, m, i, j;

  fin >> n >> m;

  for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
        cost[i][j] = INT_MAX / 2;

  int k, x, y, z, pow;
  for (i = 1; i <= m; ++i){
    fin >> x >> y >> z;
    cost[x][y] = z;
  }


  pow = 1 << n;
  for (i = 0; i < pow ;++i)
    for (j = 0; j < n; ++j)
        d[i][j]= INT_MAX / 2;

  d[1][0]=0;

  for (i = 0; i < pow; ++i)
        for (j = 0; j < n; ++j)
            if ((i & (1 << j)))
                for (k = 0; k < n; ++k)
                    if (k != j && (i & (1 << k)))
                            d[i][j] = min(d[i ^ (1 << j)][k] + cost[k][j], d[i][j]);
  x = d[pow - 1][0];

  for (i = 1;i < n; ++i)
    if(d[pow - 1][i] + cost[i][0] < x)
        x = d[pow - 1][i] + cost[i][0];

  if (x == INT_MAX / 2)
    fout << "Nu exista solutie\n";
  else
    fout << x << '\n';

  return 0;
}