#include <bits/stdc++.h>
#define VAL 20
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
int n, m, a[VAL][VAL], dp[(1 << VAL)][VAL],i,mask,j,ans = 1e9, x, y, c;;
int main()
{
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        a[x][y] = c;
    }
    int maxim = 1 << n;
    for (int mask = 0; mask < maxim; mask++)
        for (int i = 0; i < n; i++)
            dp[mask][i] = 1e9;
    dp[1][0] = 0;
    for (mask = 0; mask < maxim; mask++)
        for (i = 0; i < n; i++)
            if ((1 << i) & mask)
                for (j = 0; j < n; j++)
                    if (a[j][i] && ((1 << j) & mask))
                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + a[j][i]);
    for (j = 0; j < n; j++)
        if (a[j][0])
            if (dp[maxim-1][j] + a[j][0] < ans)
                ans = dp[maxim-1][j] + a[j][0];
    if (ans == 1e9)
        fout << "Nu exista solutie";
    else
        fout <<ans;
    return 0;
}