#include <bits/stdc++.h>
#define oo 0x3f3f3f3f 

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n, m, x, y, z;
vector<int> graf[20];
int dp[(1 << 18)][20];
int cost[20][20];

void read()
{
  f>>n>>m;
  for(int i = 0;i < n;++i)
    for(int j = 0;j < n;++j)
      cost[i][j] = oo;
  
  for(int i = 1;i <= m;++i)
    f>>x>>y, graf[y].push_back(x), f>>cost[x][y];
}

int recur(int configuration, int node)
{
  if(dp[configuration][node] == -1)
  {
    dp[configuration][node] = oo;
    
    for(auto it : graf[node])
      if(configuration & (1 << it))
        {
           if(it == 0 && configuration != (1 << node) + 1) continue; 

           dp[configuration][node] = min(dp[configuration][node], recur(configuration ^ (1 << node), it) + cost[it][node]); 
        }
  }
  return dp[configuration][node];
}

void hamilton()
{
  memset(dp, -1, sizeof(dp));
  dp[1][0] = 0;
  int result = oo;
  
  for(auto it : graf[0])
   result = min(result, recur((1 << n) - 1, it) + cost[it][0]); 
  
  if(result < oo)
    g<<result;
  else
    g<<"Nu exista solutie";
}

  
int main()
{
  read();
  hamilton();
  return 0;
}