#include <bits/stdc++.h>

using namespace std;


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

/**

dp[i][masca] = costul minim al unui drum de la 1 pana la i trecand prin noduri
                dupa bitii lui masca.

*/

int a[20][20], n , m, dp[20][262145];
int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        a[x][y] = c;
    }
    for (int i= 0; i < n; i++)
        for (int j = 0; j < (1 << n); j++)
            dp[i][j] = 2e9;
    dp[0][1] = 0;
    for (int masca = 3; masca < (1 << n); masca += 2)
        for (int i = 0; i < n; i++)
                if ((masca & (1 << i)))
                {
                    int x = masca - (1 << i);
                    for (int j = 0; j < n; j++)
                        if (a[j][i] > 0 && ((1 << j) & x) != 0)
                            dp[i][masca] = min (dp[i][masca], dp[j][x] + a[j][i]);
                }
    int sol = 2e9;
    for (int i = 1; i < n; i++)
        if (a[i][0] > 0)
            sol = min (sol, dp[i][(1 << n) - 1] + a[i][0]);
    if (sol == 2e9)
        fout << "Nu exista solutie\n";
    else fout << sol << "\n";
    return 0;
}