#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define min(a,b) ( a < b ? a : b )
#define NMAX 19
#define NMAXX 262150
#define INF 100000000
using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");
vector < int > a[NMAX];
int Cost[NMAX][NMAX], C[NMAXX][NMAX], n, m;
int main()
{
    f>>n>>m;
    //memset(Cost, INF, sizeof(Cost));
    //memset(C, INF, sizeof(C));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            //cout<<Cost[i][j]<< ' ';
            Cost[i][j] = INF;
    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < n; j++)
            C[i][j] = INF;
    for (int x, y, i = 0; i < m; i++)
    {
        f>>x>>y;
        a[y].push_back(x);
        f>>Cost[x][y];
    }
    C[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++)
                    C[i][j] = min(C[i][j], C[i ^ (1 << j)][a[j][k]] + Cost[a[j][k]][j]);
    int sol = INF;
    for (int 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";
    else g << sol;
    return 0;
}