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

using namespace std;

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

const int NMAX = 19,
          XMAX = (1 << 18),
          INF = 1 << 30;
int N, M, NN, Cost[NMAX][NMAX], C[XMAX][NMAX];
vector<int>G[NMAX];

void citire()
{
    int x, y;
    f >> N >> M;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            Cost[i][j] = INF;

    for(int i = 1; i <= M; ++i)
    {
        f >> x >> y;
        G[y].push_back(x);
        f >> Cost[x][y];
    }
    NN = (1 << N) - 1;
}

void calcul()
{
    int i, j;
    for(i = 0; i <= NN; ++i)
        for(j = 0; j < N; ++j)
            C[i][j] = INF;
    C[1][0] = 0;
    for(i = 0; i <= NN; ++i)
        for(j = 0; j < N; ++j)
            if(i & (1 << j))
                for(int &x : G[j])
                {
                    if(i & (1 << x))
                        C[i][j] = min(C[i][j], C[i ^ (1 << j)][x] + Cost[x][j]);
                }
}

int main()
{
    int Sol = INF;
    citire();
    calcul();
    for(int &nod : G[0])
    {
        Sol = min(Sol, C[NN][nod] + Cost[nod][0]);
    }
    if(Sol == INF)
        g << "Nu exista solutie";
    else g << Sol;
    return 0;
}