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

/**
dp[i][masca] = costul minim al drumului de la 0 la i, trecand prin
   nodurile marcate cu 1 in reprezentarea in baza 2 a lui masca
*/

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int a[18][18], n, m, N;
int dp[18][1 << 18];

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

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

int main()
{
    Citire();
    Dinamica();
    fout.close();
    return 0;
}