#include <bits/stdc++.h>

using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");

const int NMAX = 18;

int muc[1 + NMAX][1 + NMAX];
int n, dp[1 + (1 << NMAX)][1 + NMAX];
vector<int> g[1 + NMAX];

int main() {
    int m;
    in >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int x, y, c;
        in >> x >> y >> c;
        x ++;
        y ++;
        muc[x][y] = c;
        g[x].push_back(y);
    }
    for(int mask = 0; mask < (1 << n); mask ++)
        for(int i = 1; i <= n; i ++)
            dp[mask][i] = INT_MAX;
    dp[1][1] = 0;

    for(int mask = 0; mask < (1 << n); mask ++)
        for(int i = 1; i <= n; i ++)
            if((mask & (1 << (i - 1))) && dp[mask][i] != INT_MAX)
                for(auto it : g[i])
                    if((mask & (1 << (it - 1))) == 0)
                        dp[mask ^ (1 << (it - 1))][it] = min(dp[mask ^ (1 << (it - 1))][it], dp[mask][i] + muc[i][it]);

    int ans = INT_MAX;
    for(int i = 1; i <= n; i ++)
        if(muc[i][1])
            ans = min(ans, dp[(1 << n) - 1][i] + muc[i][1]);

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

    return 0;
}