#include <fstream>
#include <vector>

#define NMAX 20
#define KMAX 300005
#define INF 1000000000

using namespace std;

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

int n, m;
int x, y, c;
vector<pair<int, int>> l[NMAX];
int dp[KMAX][NMAX];
int lim;
int rez = INF;
int i, j;

int main()
{
    fin >>n>>m;
    for (i = 1; i <= m; ++i)
    {
        fin >>x>>y>>c;
        l[y].push_back({x, c});
    }

    lim = (1<<n) - 1;
    for (i = 0; i <= lim; ++i)
        for (j = 0; j < n; ++j)
            dp[i][j] = INF;

    dp[1][0] = 0;
    for (i = 1; i <= lim; ++i)
        for (j = 0; j < n; ++j)
            if (i & (1<<j))
                for (auto vf: l[j])
                    if (i & (1<<vf.first))
                        dp[i][j] = min(dp[i][j], dp[i^(1<<j)][vf.first] + vf.second);

    for (auto vf: l[0])
        rez = min(rez, dp[lim][vf.first] + vf.second);

    if (rez == INF) fout <<"Nu exista solutie\n";
    else
        fout <<rez<<'\n';
    fout.close();
    return 0;
}