#include <bits/stdc++.h>
#define NMAX 20
#define MMAX 600000
#define INF 0x3f3f3f3f

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

int N, M, rsp = INF;
int dp[MMAX][NMAX], cost[NMAX][NMAX];
///dp[conf][j] = costul minim a unui lant care se termina in j cu configuratia conf, i apartine configuratiei
void ciclu_hamiltonian()
{
    for (int conf = 1; conf < (1 << N); conf++)
        for (int i = 0; i < N; i++)
            if (conf & (1 << i)) ///i face parte din nodurile vizitate
                for (int j = 0; j < N; j++)
                    if ((conf & (1 << j)) == 0 && cost[i][j]) /// nu a trecut prin j
                        dp[conf + (1 << j)][j] = min(dp[conf + (1 << j)][j], dp[conf][i] + cost[i][j]);
    for (int i = 0; i < N; i++)
        if (cost[i][0])
            rsp = min(dp[(1 << N) - 1][i] + cost[i][0], rsp);
}

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
    }
    for (int conf = 1; conf < (1 << N); conf++)
        for (int i = 0; i < N; i++)
            dp[conf][i] = INF;
    dp[1][0] = 0;
    ciclu_hamiltonian();
    if (rsp == INF)
        fout << "Nu exista solutie";
    else fout << rsp;
    return 0;
}