#include <cstring>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
 
#define MAXN 18
#define inf 0x3f3f3f3f
 
typedef vector<int>::iterator iter;
 
ifstream f("hamilton.in");
ofstream g("hamilton.out");
 
int n, m;
int c[1 << MAXN][MAXN]; // c[i][j] == costul minim al unui drum care trece prin nodurile din multimea i si se termina in j.
int d[MAXN][MAXN];
vector<int> G[MAXN];
 
int main()
{
    memset(d, 0x3f, sizeof(d));
    memset(c, 0x3f, sizeof(c));
 
    f >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        f >> x >> y >> c;
        G[y].push_back(x);
        d[x][y] = c;
    }
 
    c[1][0] = 0;
    for (int i = 1; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) == 0) {
                continue;
            }
 
            for (iter it = G[j].begin(); it != G[j].end(); it++) {
                if ((i & (1 << *it)) == 0) {
                    continue;
                }

                c[i][j] = min(c[i][j], c[i ^ (1 << j)][*it] + d[*it][j]);
            }
        }
    }
 
    int mn = inf;
    for (iter it = G[0].begin(); it != G[0].end(); it++) {
        mn = min(mn, c[(1 << n) - 1][*it] + d[*it][0]);
    }
 
    if (mn == inf) {
        g << "Nu exista solutie" << endl;
    } else {
        g << mn << endl;
    }
 
    return 0;
}