#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 = 1e9;

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;

    for(int i = 0; i < n; ++i)
        dp[1][i] = 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 mask = (1<<n) - 1;
    int minim = INF, ind;
    for(int i = 0; i < n; ++i)
        if(minim > dp[mask][i]) {
            minim = dp[mask][i];
            ind = i;
        }
    int ans = minim;
    if(minim != INF) {
        int cop = ind;
        while(mask) {
            for(int i = 0; i < n; ++i)
                if(dp[mask/2][i] + cost[i][ind] == dp[mask][ind]) {
                    ind = i;
                    break;
                }
            mask /= 2;
        }
        minim = min(INF, cost[cop][ind]);
        if(minim == INF)
            fout << "Nu exista solutie";
        else
            fout << ans + minim;

    } else
        fout << "Nu exista solutie";



    return 0;
}