#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 18

using namespace std;

vector<vector<int>> v, cost;
int d[MAXN][2 << MAXN];

int noNodes, n, firstNode;

int getCost(int j, int mask, int s){
//  printf("%d ", j);
//  int mk = mask;
//  for(int i = n - 1; i >= 0; i --){
//    if(mk >= 1 << i){
//      printf("1");
//      mk -= 1<<i;
//    }
//    else
//      printf("0");
//  }
//  printf("\n");

  if(d[j][mask] != 0)
    return d[j][mask];

  noNodes ++; /// Mai folosim inca un nod

  int k, x, min = -1;
  for(k = 0; k < v[j].size(); k ++){
    /// Daca toate nodurile sunt folosite si ajungem la primul
    if(noNodes == n && v[j][k] == firstNode){
//      printf("----- ok ------\n");
      noNodes --;
      d[j][mask] = s + cost[j][k];
      return s + cost[j][k];
    }

    if(!(mask & (1 << v[j][k]))){ /// Daca nu am mai folosit nodul o data
      x = getCost(v[j][k], mask | (1 << v[j][k]), s + cost[j][k]); /// Vedem cat ar costa ciclul din acel punct
      if(min == -1 || x < min)
        min = x;
    }
  }

  noNodes --;
  d[j][mask] = min;
  return min;
}

int main(){
  int i, a, b, c, m;

  ifstream fin("hamilton.in");
  fin >> n >> m;
  v.resize(n);
  cost.resize(n);

  for(i = 0; i < m; i ++){
    fin >> a >> b >> c;

    v[a].push_back(b);
    cost[a].push_back(c);
  }
  fin.close();

  noNodes = 0;
  firstNode = 0;

  ofstream fout("hamilton.out");
  fout << getCost(0, 1 << firstNode, 0) << endl;
  fout.close();
  return 0;
}