#include <bits/stdc++.h>
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
///          nod  cost
int a[20][20];
int dp[20][(1 << 18) + 2];
int n, m, N;
/**
dp[i][masca] = costul minim al drumului de la 0 la i,
  trecand deja prin nodurile marcate cu 1 in
  reprezentarea in baza 2 a lui masca
*/

void Citire()
{
    int i, j, k, cost;
    fin >> n >> m;
    N = (1 << n);
    for (k = 1; k <= m; k++)
    {
        fin >> i >> j >> cost;
        a[i][j] = cost;
    }
    fin.close();
}

void Dinamica()
{
    int oo = 2e9;
    int i, j, masca, x;
    for (i = 0; i < n; i++)
        for (j = 1; j < N; j++)
            dp[i][j] = oo;
    /// init:
    dp[0][1] = 0; /// masca = 00001
    for (masca = 3; masca < N; masca += 2)
        for (i = 1; i < n; i++)
            if (masca & (1 << i))
        {
          x = masca ^ (1 << i);
          for (j = 0; j < n; j++)
            if ((x & (1 << j)) && (a[j][i] > 0))
              dp[i][masca] = min(dp[i][masca], dp[j][x]+a[j][i]);
        }
    x = oo;
    for (i = 1; i < n; i++)
        if (dp[i][N - 1] < oo && a[i][0] > 0)
            x = min(x, dp[i][N - 1] + a[i][0]);
    if (x == oo) fout << "Nu exista solutie\n";
    else fout << x << "\n";
    fout.close();
}

int main()
{
    Citire();
    Dinamica();
    return 0;
}