#include <fstream>
#define N 20
#include <vector>
#define INF 2000000000

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

int sol[1 << N][N];
struct bla
{
    int ve, co;
};
vector <bla> graph[N];

int main()
{
    int n, m, x, y, c, fara, nod;
    f >> n >> m;
    while (m--)
    {
        f >> x >> y >> c;
        graph[x].push_back({ y,c });
    }
    for (int i = 0;i < (1 << n);++i)///2^n-1 in reprezentarea binara are toti bitii 1
        for (int j = 0;j < n;++j)
            sol[i][j] = INF;
    sol[1][0] = 0;
    for (int i = 2;i < (1 << n);++i)
        for (int j = 0;j < n;++j)
            if ((i & (1 << j)) != 0)
            {
                fara = i ^ (1 << j);
                nod = j;
                for (int k = 0;k < graph[nod].size();++k)
                {
                    int vee = graph[nod][k].ve;
                    int cost = graph[nod][k].co;
                    if ((i & (1 << vee)) != 0)
                        sol[i][j] = min(sol[i][j], sol[fara][vee] + cost);
                }
            }
    int mi = INF;
    nod = 0;
    ///fiecare bit de 1 din reprezentarea binara a lui 1<<n-1 marchiaza faptul ca nodul de pe pozitia i exista
    ///dar nodul 0 nu se gaseste
    for (int k = 0;k < graph[nod].size();++k)
    {
        int vee = graph[nod][k].ve;
        int cost = graph[nod][k].co;
        mi = min(mi, sol[(1 << n) - 1][vee] + cost);
    }
    if (mi != INF)
        g << mi << '\n';
    else
        g << "Nu exista solutie";
    f.close();
    g.close();
    return 0;
}