#include <bits/stdc++.h>

using namespace std;

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

int dp[18][(1 << 18) + 2];
int a[20][20], n, m;

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

int main()
{
    int x;
    Citire();
    int N = (1 << n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < N; j++)
            dp[i][j] = 2e9;
    dp[0][1] = 0;
    for (int masca = 3; masca < N; masca += 2)
        for (int i = 1; i < n; i++)
            if (masca & (1 << i))
            {
                x = masca ^ (1 << i);
                for (int 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 (int 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;
    return 0;
}