#include <bits/stdc++.h>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
#define inf 0x3f3f3f3f

int n, m, a, b, c;
int path[18][18];
int dp[1 << 18][18];

int main(void)
{
    cin >> n >> m;
    memset(path, -1, sizeof path);
    while (m--)
    {
        cin >> a >> b >> c;
        path[a][b] = c;
    }
    memset(dp, inf, sizeof dp);
    dp[1][0] = 0;
    for (int mask = 0; mask < (1 << n); ++mask)
    {
        for (int i = 0; i < n; ++i)
        {
            if (mask & (1 << i))
            {
                for (int j = 0; j < n; ++j)
                {
                    if (~path[i][j])
                    {
                        if (!(mask & (1 << j)))
                        {
                            dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + path[i][j]);
                        }
                    }
                }
            }
        }
    }
    int sol = inf;
    for (int i = 0; i < n; ++i)
        if (path[i][0] > 0)
            sol = min(sol, dp[(1 << n) - 1][i] + path[i][0]);
    if (sol != inf)
        cout << sol;
    else
        cout << "Nu exista solutie";
    return 0;
}