#include <bits/stdc++.h>
using namespace std;

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

const int INF = INT_MAX / 2;
int n, m;
int mat[20][20];
int dp[1 << 20][20];

int main() {
    ios::sync_with_stdio(false);
    fin.tie(nullptr);

    fin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        mat[x][y] = c;
    }

    int full = (1 << n);

    for (int mask = 0; mask < full; mask++)
        for (int j = 0; j < n; j++)
            dp[mask][j] = INF;

    dp[1][0] = 0; // start at node 0, mask = 000...001

    for (int mask = 1; mask < full; mask++) {
        for (int last = 0; last < n; last++) {
            if (!(mask & (1 << last))) continue;
            if (dp[mask][last] == INF) continue;

            for (int nxt = 0; nxt < n; nxt++) {
                if (mat[last][nxt] && !(mask & (1 << nxt))) {
                    dp[mask | (1 << nxt)][nxt] = min(
                        dp[mask | (1 << nxt)][nxt],
                        dp[mask][last] + mat[last][nxt]
                    );
                }
            }
        }
    }

    int ans = INF;
    for (int i = 1; i < n; i++) {
        if (mat[i][0]) {
            ans = min(ans, dp[full - 1][i] + mat[i][0]);
        }
    }

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

    return 0;
}