#include <bits/stdc++.h>
#define NMAX 20

using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");

int n, m, a[NMAX][NMAX], dp[(1 << NMAX)][NMAX];

int main()
{
    int x, y, c;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        a[x][y] = c;
    }

    int maxim = 1 << n;
    for (int mask = 0; mask < maxim; mask++)
        for (int i = 0; i < n; i++)
            dp[mask][i] = 1e9;

    dp[1][0] = 0;

    for (int mask = 0; mask < maxim; mask++)
        for (int i = 0; i < n; i++)
            if ((1 << i) & mask)
                for (int j = 0; j < n; j++)
                    if (a[j][i] && ((1 << j) & mask))
                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + a[j][i]);
    int rezultat = 1e9;
    for (int j = 0; j < n; j++)
        if (a[j][0])
            if (dp[maxim-1][j] + a[j][0] < rezultat)
                rezultat = dp[maxim-1][j] + a[j][0];
    if (rezultat == 1e9)
        fout << "Nu exista solutie";
    else
        fout <<rezultat;
    return 0;
}