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

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

void usain_bolt()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
}

void solve()
{
    int n, m;
    fin >> n >> m;
    vector<vector<int>> a(n, vector<int>(n, -1));
    vector<vector<int>> dp((1 << n), vector<int>(n, -1));
    for (; m; --m) {
        int x, y, w;
        fin >> x >> y >> w;
        a[x][y] = w;
    }
    dp[1][0] = 0;
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            if (!(i & (1 << j))) {
                continue;
            }
            if (dp[i][j] == -1) {
                continue;
            }
            for (int k = 0; k < n; ++k) {
                if (i & (1 << k)) {
                    continue;
                }
                if (a[j][k] == -1) {
                    continue;
                }
                if (dp[i ^ (1 << k)][k] == -1) {
                    dp[i ^ (1 << k)][k] = dp[i][j] + a[j][k];
                } else {
                    dp[i ^ (1 << k)][k] = min(dp[i ^ (1 << k)][k], dp[i][j] + a[j][k]);
                }
            }
        }
    }
    int mn = int(2e9);
    for (int i = 0; i < n; ++i) {
        if (dp[(1 << n) - 1][i] == -1 || a[i][0] == -1) {
            continue;
        }
        mn = min(mn, dp[(1 << n) - 1][i] + a[i][0]);
    }

    if (mn == 2e9) {
        fout << "Nu exista solutie\n";
    } else {
        fout << mn << '\n';
    }

    return;
}

int main()
{
    usain_bolt();
    
    int tt = 1;

    while (tt--) {
        solve();
    }
    return 0;
}