#include <bits/stdc++.h>
using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");
// #define f cin
// #define g cout
vector<pair<int, int>> v[19];
int n, m, dp[263000][19];
int solve(int, int);
int32_t main()
{
    memset(dp, 0x3f3f3f3f, sizeof dp);
    f >> n >> m;
    for (int x, y, c; m; m--)
    {
        f >> x >> y >> c;
        v[x].push_back({y, c});
    }
    int x = solve(2, 1);
    if (x == (0x3f3f3f3f))
        g << "Nu exista solutie";
    else
        g << x;
    return 0;
}

int solve(int config, int lst)
{
    if (dp[config][lst] == (0x3f3f3f3f))
    {
        if (__builtin_popcount(config) == n)
        {
            int cst = -1;
            for (const auto &i : v[lst])
                if (i.first == 0)
                    cst = i.second;
            if (cst != -1)
                dp[config][lst] = cst;
        }
        else
        {
            for (const auto &i : v[lst])
                if (!(config & (1 << i.first)))
                    dp[config][lst] = min(dp[config][lst],
                                          i.second + solve((config | (1 << i.first)), i.first));
        }
    }
    return dp[config][lst];
}