#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

const string file = "hamilton";
const ll INF = 9223372036854775807ll;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, inf = 2147483647, nmax = 20;

int n, m, c[nmax][nmax], pd[(1<<nmax)+5][nmax];

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int x, y, z;
        fin >> x >> y >> z;
        c[x][y] = z;
    }
    for (int i = 0; i < (1<<n); ++i)
        for (int j = 0; j < n; ++j)
            pd[i][j] = inf;
    pd[1][0] = 0;
    int mn = inf;
    for (int conf = 1; conf < (1<<n); ++conf)
        for (int last = 0; last < n; ++last){
            if(pd[conf][last] != inf && conf == (1<<n)-1){
                if(c[last][0] == 0)
                    pd[conf][last] = inf;
                else pd[conf][last] += c[last][0];
                mn = min(mn, pd[conf][last]);
                continue;
            }
            if(pd[conf][last] != inf)
                for (int i = 0; i < n; ++i)
                    if(c[last][i] != 0 && (conf&(1<<i)) == 0)
                        pd[conf^(1<<i)][i] = min(pd[conf^(1<<i)][i], pd[conf][last]+c[last][i]);
        }
    if(mn == inf)
        fout << "Nu exista solutie\n";
    else fout << mn << "\n";
    return 0;
}