#include <fstream>
#include <iostream>
#include <vector>
#define NMAX 25
#define PMAX 1050000
#define INF 0x3f3f3f3f
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
vector<vector<pair<int, int> > > gr;
int N, M;
int c[PMAX][NMAX];
void read() {
    fin >> N >> M;
    int x, y, z;
    gr.resize(N + 1);
    for (int i = 0; i < M; ++i) {
        fin >> x >> y >> z;
        gr[y].push_back(make_pair(x, z));
    }
}
void setup() {
    for (int i = 0; i < (1 << N); ++i) {
        for (int j = 0; j < N; ++j) {
            c[i][j] = INF;
        }
    }
}
void afiseazaBinar(int nr) {
    for (int i = 0; i < N; ++i) {
        if ((1 << i) & nr) {
            cout << 1;
        }
        else
            cout << 0;
    }
    cout << " ";
}
void solve() {
    c[1][0] = 0;
    for (int i = 0; i < (1 << N); ++i) {
        for (int j = 1; j < N; ++j) {
            int mask = (1 << j);
            if ((i & mask) != 0) {
                for (auto v : gr[j]) {
                    c[i][j] = min(c[i][j], c[i ^ mask][v.first] + v.second);
                }
            }
        }
    }
}
void afis() {
    int mini = INF;
    for (auto v : gr[0]) {
        mini = min(mini, c[(1 << N) - 1][v.first] + v.second);
    }
    if (mini != INF)
        fout << mini << "\n";
    else
        fout << "Nu exista solutie\n";
}
int main()
{
    read();
    setup();
    solve();
    afis();
    return 0;
}