/// Created by IDorando-Senapi
/// Arigatou
#include <bits/stdc++.h>
#define INF 2e9
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n, dp[1 << 19][20], m, cost[20][20];

int main()
{
    int i, j, mask, N, x, sol = INF, y, c;
    fin >> n >> m;
    N = (1 << n);
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        cost[x][y] = c;
    }

    for (mask = 0; mask < N; mask++)
        for (i = 0; i < n; i++)
            dp[mask][i] = INF;

    dp[1][0] = 0;
    for (mask = 3; mask < N; mask += 2)
        for (i = 0; i < n; i++)
            if (mask & (1 << i))
            {
                x = mask - (1 << i);
                for (j = 0; j < n; j++)
                    if (x & (1 << j) and cost[j][i])
                        dp[mask][i] = min(dp[mask][i], dp[x][j] + cost[j][i]);
            }

    for (i = 1; i < n; i++)
        if (cost[i][0])
        sol = min(sol, dp[N - 1][i] + cost[i][0]);

    if (sol == INF)
        fout << "Nu exista solutie\n";
    else
        fout << sol << "\n";


    return 0;
}