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