#include <fstream>
#include <vector>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int inf = 500000000;
int N, M;
vector <int> G[20];
int D[20][20];
int dp[19][(1 << 19)]; //dp[i][j] - costul minim de a ajunge in nodul i, avand starea j

int main()
{
    f >> N >> M;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            D[i][j] = inf;
    for (int i = 1; i <= M; ++i)
    {
        int x, y, c;
        f >> x >> y >> c;
        G[y].push_back(x);
        D[x][y] = c;
    }
    for (int i = 0; i < N; ++i)
        for (int s = 0; s < (1 << N); ++s)
            dp[i][s] = inf;
    dp[0][1] = 0;
    for (int s = 0; s < (1 << N); ++s)
        for (int i = 0; i < N; ++i)
            if (s & (1 << i))
                for (const int & j : G[i])
                    if (s & (1 << j))
                        dp[i][s] = min(dp[i][s], dp[j][s ^ (1 << i)] + D[j][i]);
    int ans = inf;
    for (const int & x : G[0])
        ans = min(ans, dp[x][(1 << N) - 1] + D[x][0]);
    if (ans == inf)
        g << "Nu exista solutie";
    else
        g << ans;
    f.close();
    g.close();
    return 0;
}