#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[18][(1 << 18)]; //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 (int j = 0; j < G[i].size(); ++j)
                    if (s & (1 << G[i][j]))
                        dp[i][s] = min(dp[i][s], dp[G[i][j]][s ^ (1 << i)] + D[G[i][j]][i]);
    int ans = inf;
    for (int i = 0; i < G[0].size(); ++i)
            ans = min(ans, dp[G[0][i]][(1 << N) - 1] + D[G[i][0]][0]);
    if (ans == inf)
        g << "Nu exista solutie";
    else
        g << ans;
    f.close();
    g.close();
    return 0;
}