#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
 
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n, m, x, y, z, rez = oo, cost[25][25];
vector<int> graf[25];
int dp[(1 << 18) + 5][25];
 
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 calc(int conf, int last)
{
  if(dp[conf][last] == -1)
  {
    dp[conf][last] = oo;

    for(auto it : graf[last])
      if(conf & (1 << it))
      {
        if(it == 0 && conf != (1 << last) + 1) continue;

        dp[conf][last] = min(dp[conf][last], calc(conf ^ (1 << last), it) + cost[it][last]);
      }
  }
  return dp[conf][last];
}

void Solve()
{
  memset(dp, -1, sizeof(dp));
  dp[1][0] = 0;

  for(auto it : graf[0])
    rez = min(rez, calc((1 << n) - 1, it) + cost[it][0]);

  if(rez == oo) g<<"Nu exita solutie"<<'\n';
  else g<<rez;
}
 
int main()
{
  Read();
  Solve();
  return 0;
}