#include <iostream>
#include <bits/stdc++.h>

#define inf 1e9
#define siz 19

using namespace std;

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

int n,m;
int best[siz][1 << siz];

vector<pair<int,int>> g[siz]; // nod si cost. 0 indexed
int muchie[siz][siz];


int main()
{
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int from, to, cost;
        in >> from >> to >> cost;
        g[from].push_back({to, cost});
        muchie[from][to] = cost;
    }

    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j < 1 << siz; j++)
            best[i][j] = inf;
    }

    best[0][1] = 0;

    for (int bset = 1; bset < (1 << n); ++bset)
    {
        for (int i = 0; i < n; ++i)
        {
            if (best[i][bset] == inf) continue;
            for (auto vc : g[i])
            {
                int v = vc.first;
                int c = vc.second;
                if (bset & (1 << v))
                {
                    continue;
                }
                int bnew = bset | (1 << v);
                if (best[v][bnew] > best[i][bset] + c) {
                    best[v][bnew] = best[i][bset] + c;
                }
            }
        }
    }

    int ret = inf;
    for (int i=1; i<n; ++i)
    {
        if (best[i][(1 << n) - 1] != inf)
            if (muchie[i][0])
            {
                ret = min(ret, best[i][ (1 << n) - 1] + muchie[i][0]);
            }
    }

    if (ret == inf)
        out << "Nu exista solutie";
    else
        out << ret;

    return 0;
}