#include <bits/stdc++.h>

#define MAXN 22
#define MAXK (1 << MAXN) - 1
#define inf 25000000

using namespace std;

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

struct two{
    int nod, c;
};

queue <int> Q;
vector <two> graph[MAXN];

int n, m, dp[MAXK][MAXN];

inline void Read() {
    int x, y, z;

    fin >> n >> m;

    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> z;

        graph[y].push_back({x, z}); ///construiesc graful transpus
    }
}

inline void Dynamics() {

    int nn, mask;

    nn = (1 << n) - 1;

    dp[1][0] = 0; ///plec din 0

    for (int i = 1; i <= nn; i++) {
        for (int j = 0; (1 << j) <= i; j++) {
            dp[i][j] = inf;
            dp[1][0] = 0;

            if (i & (1 << j)) {
                mask = i - (1 << j);

                for (auto x : graph[j]) {
                    if (mask & (1 << (x.nod))) {
                        dp[i][j] = min(dp[i][j], dp[mask][x.nod] + x.c);
                    }
                }
            }
        }
    }

    int minim = inf;

    for (auto x : graph[0]) {
        minim = min(minim, dp[nn][x.nod] + x.c); ///unesc nodul nod cu 0
    }

    if (minim != inf) {
        fout << minim;
    }
    else
        fout << "Nu exista solutie!";
}

int main () {
    Read();
    Dynamics();

    fin.close(); fout.close(); return 0;
}