#include <bits/stdc++.h>
#define Nmax (1 << 18) + 5
#define DIM 19
#define INF 2e9
using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int N, M;
vector<pair<int, int> > G[DIM];
int dp[DIM][Nmax], dist[DIM][DIM];
int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y, c;
        f >> x >> y >> c;
        dist[y][x] = c;
    }

    for (int i = 0; i < N; ++i)
    for (int msk = 1; msk < (1 << N); ++msk)
       dp[i][msk] = INF;
    dp[0][1] = 0;

    for (int msk = 1; msk < (1 << N); ++msk)
    for (int i = 1; i < N; ++i)
    for (int j = 0; j < N; ++j)
       if (dist[i][j] && (msk & (1 << j)) && (msk & (1 << i)))
           dp[i][msk] = min(dp[i][msk], dp[j][msk - (1 << i)] + dist[i][j]);

    int ans = INF;
    for (int i = 1; i < N; ++i)
        if (dist[0][i]) ans = min(ans, dp[i][(1 << N) - 1] + dist[0][i]);

    if (ans < INF) g << ans << '\n';
    else cout << "Nu exista ciclu\n";

    return 0;
}