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

#define siz 18
#define inf 1e9

using namespace std;

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

int best[siz][1 << siz];
vector<pair<int, int>> la[siz];
int cost[siz][siz];
int n, m;

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

    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 << siz; bset ++)
    {
        for (int from = 0; from < n; from++)
        {
            if (best[from][bset] == inf)
                continue;
            for (auto& per: la[from])
            {
                int to = per.first;
                int c = per.second;

                if (bset & (1 << to))
                    continue;
                int bset_new = bset | (1 << to);

                if (best[to][bset_new] > best[from][bset] + c)
                {
                    best[to][bset_new] = best[from][bset] + c;
                }
            }
        }
    }

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

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

    return 0;
}