#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector<pair<int, int> > a[18];

int cost[18][18];

int dp[1 << 18][18];

int n, m, i, j, next, c,mask;

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

    }
    for (int i = 0; i < (1<<n); i++)
        {
            for (int j = 0; j < n; j++)
            {
                dp[i][j] = 1e9;
            }
        }

    dp[1][0] = 0;

    for (mask = 0; mask < (1<<n); mask++)
    {
        for (j = 0; j < n; j++)
        {
            if (mask & (1 << j))
            {
                for (auto & x : a[j])
                {
                    int next = x.first, c = x.second;
                    if (!(mask & (1 << next)))
                    {
                        dp[mask | (1 << next)][next] = min(dp[mask | (1 << next)][next], dp[mask][j] + c);
                    }
                }
            }
        }
    }

    int ans = 1e9;
    for(i = 0; i < n; i++)
    {
        if (cost[i][0])
            ans = min(ans, dp[mask - 1][i] + cost[i][0]);
    }

    if (ans == 1e9)
        {
            fout << "Nu exista solutie";
        }
    else
    {
        fout << ans;
    }


}