#include <bits/stdc++.h>
#define BITS 18

using namespace std;

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

int n, m, x, y, c;
int dp[(1 << BITS) - 1][BITS + 5], Ans = INT_MAX;
vector < pair < int, int > > G[BITS + 5], Reverse[BITS + 5];

int main()
{
    fin >> n >> m;
    while (m--)
    {
        fin >> x >> y >> c;
        G[x].push_back({c, y});
        Reverse[y].push_back({c, x});
    }

    for (int mask = 0; mask < (1 << n); mask++)
        for (int i = 0; i < n; i++)
            dp[mask][i] = INT_MAX / 2;

    dp[1][0] = 0;
    for (int mask = 0; mask < (1 << n); mask++)
        for (int i = 0; i < n; i++)
            if (mask & (1 << i))
                for (int j = 0; j < G[i].size(); j++)
                    if (!(mask & (1 << G[i][j].second)))
                        dp[mask | (1 << G[i][j].second)][G[i][j].second] = min(dp[mask | (1 << G[i][j].second)][G[i][j].second], dp[mask][i] + G[i][j].first);

    for (int i = 0; i < Reverse[0].size(); i++)
        Ans = min(Ans, dp[(1 << n) - 1][Reverse[0][i].second] + Reverse[0][i].first);

    if (Ans != INT_MAX / 2)
        fout << Ans;
    else
        fout << "Nu exista solutie";
    return 0;
}