#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <iomanip>
#define ll long long
#define lsb(x) (x & -x)

using namespace std;

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

const int INF = 1e9;

int main() {

    int n, m;
    in >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    vector<pair<int, int>> aux;
    for(int i = 1; i <= m; i ++) {
        int x, y, c;
        in >> x >> y >> c;
        g[x].push_back({y, c});
        if(y == 0)
            aux.push_back({x, c});
    }

    vector<vector<int>> dp((1 << n), vector<int> (n, INF));
    dp[1][0] = 0;

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

            for(auto it : g[i])
                if(((1 << it.first) & mask) == 0)
                    dp[mask ^ (1 << it.first)][it.first] = min(dp[mask ^ (1 << it.first)][it.first], dp[mask][i] + it.second);
        }
    }

    int ans = INF;
    for(auto it : aux)
        ans = min(ans, dp[(1 << n) - 1][it.first] + it.second);

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

    return 0;
}