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

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

int main() {
    int n, m; fin >> n >> m;
    vector<vector<int>> in(n), ad(n, vector<int>(n, 1e9));
    for (int i = 0; i < m; i++) {
        int x, y, z; fin >> x >> y >> z;
        in[y].push_back(x); ad[x][y] = z;
    }

    vector<vector<int>> dp(1 << n, vector<int>(n, 1e9));
    dp[1][0] = 0;
    for (int mask = 3; mask < (1 << n); mask += 2) // Parcurg submulțimile.
        for (int i = 1; i < n; i++) // Parcurg biții din mask.
            if (mask & (1 << i)) // Testez dacă bitul e setat la 1.
                for (int j : in[i]) // Dacă da, parcurg nodurile j care intră în i.
                    dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + ad[j][i]); // Actualizez dp-ul.

    int sol = 1e9;
    for (int i = 1; i < n; i++)
        sol = min(sol, dp[(1 << n) - 1][i] + ad[i][0]);
    if (sol == 1e9)
        fout << "Nu exista solutie\n";
    else
        fout << sol << '\n';
    return 0;
}