#include <iostream>
#include <fstream>
#define inf 1 << 30
using namespace std;
int n, m, cost[20][20], dp[1 << 18][20];
void read()
{
    ifstream fin("hamilton.in");
    fin >> n >> m;
    int x, y , c;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
         cost[i][j] = inf;
    for(int i = 1; i <= m; ++i){
        fin >> x >> y >> c;
        cost[x][y] = c;
    }
}
void hamilton()
{
    int sol = inf;
    for(int i = 0; i < (1 << n); ++i)
      for(int j = 0; j < n; ++j)
        dp[i][j] = inf;
    dp[1][0] = 0;
    for(int i = 1; i < (1 << n); ++i)
      for(int j = 0; j < n; ++j)
        if(i & (1 << j)) /// daca j se afla in lantul i
         for(int k = 0; k < n; ++k)
           if(cost[k][j] != inf && i & (1 << k)) /// daca exista muchie de la k la j si k e din lantul i
             dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + cost[k][j]);
    for(int i = 0; i < n; ++i)
        if(cost[i][0] != inf)
          sol = min(sol, dp[(1 << n) - 1][i] + cost[i][0]);
   ofstream fout("hamilton.out");
   if(sol == inf) fout << "Nu exista solutie";
    else  fout << sol;
}
int main()
{
    read();
    hamilton();
    return 0;
}