#include <iostream>
#include <fstream>
#include <vector>
const int stari = 262150;   //262144 e 2^18
const int oo = 2e9;

int N, M;
int cost[20][20];
int d[stari][20];
using namespace std;

vector <int> A [20];

int main()
{
    ifstream in ("hamilton.in");
    ofstream out ("hamilton.out");

    in >> N >> M;
    int x, y;
    int sol;

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cost[i][j] = oo;    //initializam matricea de adiacenta cu 8 intors

    for (int i = 0; i < M; ++i)
    {
        in>>x>>y;
        A[y].push_back(x);
        in>>cost[x][y];
    }

    for(int i = 0; i < (1<<N); ++i)
        for(int j = 0; j < N; ++j)
            d[i][j] = oo;

    d[1][0] = 0;

    for (int i = 0; i < (1<<N); ++i)
        for (int j = 0; j < N; ++j)
            if(i && (1<<j))
                for(int k = 0; k < A[j].size(); ++k)
                    if(i && (1<<A[j][k]))   //un vecin de-a lu j care are muchie spre j
                        d[i][j] = min(d[i][j], d[i ^ (1<<j)][A[j][k]] + cost[A[j][k]][j]);

    sol = oo;
        for (size_t i = 0; i < A[0].size(); ++i)
            sol = min(sol, d[(1<<N) - 1][A[0][i]] + cost[A[0][i]][0]);

    if (sol == oo)
        out << "Nu exista solutie" << endl;
    else
        out << sol << endl;
    //int sa;

    //sa = 0x7fffffff;
    //cout<<sa<<"\n";;
    //sa = (1<<31);
    //cout<<sa;



}