#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

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

const int maxMask = 3e5 + 5;
const int maxN = 20;
const int INF = 1e8;

vector <int> g[maxN];
int dp[maxMask][maxN];
int cost[maxN][maxN];

int main() {

    int n, m; fin >> n >> m;

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cost[i][j] = INF;

    for(int i = 1; i <= m; ++i) {
        int u, v, c; fin >> u >> v >> c;
        g[u].push_back(v);
        cost[u][v] = c;
    }

    for(int i = 0; i < (1 << n); ++i)
        for(int j = 0; j < n; ++j)
            dp[i][j] = INF;

    dp[1][0] = 0;

    for(int mask = 1; mask < (1 << n); ++mask)
        for(int v = 0; v < n; ++v)
            if((mask & (1<<v)))
                for(int u : g[v])
                    if(!(mask & (1 << u)))
                        dp[mask | (1 << u)][u] = min(dp[mask | (1 << u)][u],
                                                     dp[mask][v] + cost[v][u]);

    int minim = INF, mask = (1<<n) - 1;
    for(int i = 0; i < n; ++i)
        minim = min(minim, dp[mask][i] + cost[i][0]);

    if(minim == INF)
        fout << "Nu exista solutie";
    else
        fout << minim;

    return 0;
}