#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 rezultat (int i, int n) {
    int ind = i, mask = (1 << n) - 1;

    if(dp[mask][i] == INF) return INF;
    while(mask != 1) {
        int ok = 0;
        for(int k = 0; k < n; ++k) {
            int mask2 = (mask ^ (1<<ind));
            if(dp[mask2][k] + cost[k][ind] == dp[mask][ind]) {
                ind = k;
                ok = 1;
                mask = mask2;
                k = n + 1;
            }
        }
        if(ok == 0){
            return INF;
        }
    }
    int ans = min(INF, cost[i][ind]);

    if(ans == INF)
        return INF;

    return dp[(1<<n)-1][i] + ans;
}

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;
    for(int i = 0; i < n; ++i)
        minim = min(minim, rezultat(i, n));

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

    return 0;
}