#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 18;
const int INF = 100000000;

int N, M;
vector < pair <int, int> > g[NMAX + 5];

int dp[NMAX + 5][(1 << NMAX) + 5];

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        g[y].push_back({x, c});
    }

    for(int i = 0; i < N; i++)
        for(int mask = 0; mask < (1 << N); mask++)
            dp[i][mask] = INF;

    dp[0][1] = 0;

    for(int mask = 1; mask < (1 << N); mask++)
        for(int f = 0; f < N; f++)
            if(mask & (1 << f))
                for(auto it : g[f])
                    if(mask & (1 << it.first))
                        dp[f][mask] = min(dp[f][mask], dp[it.first][mask ^ (1 << f)] + it.second);

    int ans = INF;

    for(auto it : g[0])
        ans = min(ans, dp[it.first][(1 << N) - 1] + it.second);

    if(ans >= INF)
        fout << "Nu exista solutie\n";
    else
        fout << ans << '\n';

    return 0;
}