#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(n, vector<int> ((1 << n), INF));
    dp[0][1] = 0;

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

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

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

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

    return 0;
}