#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

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

const int MAXN = 20;
const int MAX = 262150;
const int INF = 100000000;

int N,M,x,y,i;
vector <int> A[MAXN];
int Cost[MAXN][MAXN], C[MAX][MAXN];

void citire()
{
    f >> N >> M;
    for (i = 1; i <= M; i++)
    {
        f >> x >> y;
        A[y].push_back(x);
        f >> Cost[x][y];
    }
    f.close();
}

int main()
{
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            Cost[i][j] = INF;

    // folosesc liste de vecini pentru retinerea grafului
    citire();

    for (int i = 0; i < 1 << N; ++i)
        for (int j = 0; j < N; ++j)
            C[i][j] = INF;

    C[1][0] = 0;

    for (int i = 0; i < 1 << N; ++i)
        for (int j = 0; j < N; ++j)
            if (i & (1<<j))
                for (size_t k = 0; k < A[j].size(); ++k)
                    if (i & (1<<A[j][k]))
                        // recurenta este C[i][j][k] = min{C[i][j xor 2k][v] + Cost[v][k]},
                        C[i][j] = min(C[i][j], C[i ^ (1<<j)][ A[j][k] ] + Cost[ A[j][k] ][j]);

    int Sol = INF;
    for (size_t i = 0; i < A[0].size(); ++i)
        Sol = min(Sol, C[(1<<N) - 1][ A[0][i] ] + Cost[ A[0][i] ][0]);

    if (Sol == INF)
        g << "Nu exista solutie" << endl;
    else
        g << Sol << endl;

    g.close();
    return 0;
}