#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <climits>
#define MAXN 20
#define MAXX 262150 // aproximativ 2 ^ 18
using namespace std;

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

vector <int> v[MAXN];
int n, m, sol;
int c[MAXX][MAXN];
int cost[MAXN][MAXN];

void init()
{
    sol = INT_MAX;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cost[i][j] = INT_MAX;
    //memset(c, -1, sizeof(c)); //valoarea int -1 este convertita in unsigned char, luand valoarea 255, adica toti cei 8 biti au valoarea 1
    //echivalent:
    for (int i = 0; i < 1<<n; ++i)
        for (int j = 0; j < n; ++j)
            c[i][j] = INT_MAX;
}

void read()
{
    int x, y;

    init();
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        fin >> x >> y;
        v[y].push_back(x); //RETINEM ARCUL INVERS
        fin >> cost[x][y];
    }
}

void solve()
{
    init();
    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 < v[j].size(); ++k)
                    if (i & (1 << v[j][k]))
                        c[i][j] = min(c[i][j], c[i ^ (1 << j)][v[j][k]] + cost[v[j][k]][j]);
            }
    for (size_t i = 0; i < v[0].size(); ++i)
        sol = min(sol, c[(1<<n) - 1][v[0][i]] + cost[v[0][i]][0]);
}

void write()
{
    if (sol == INT_MAX)
        fout << "Nu exista solutie\n";
    else
        fout << sol << '\n';
}

int main()
{
    read();
    solve();
    write();
    return 0;
}