#include <bits/stdc++.h>

using namespace std;
int n, m, a[20][20], dp[1 << 20][20], N, mask, Mask, x, y, i, j, c, sol;
int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(; m; m--)
    {
        scanf("%d%d%d", &x, &y, &c);
        a[x][y] = c;
    }
    for(i = 0; i < n - 1; i++)
        dp[1 << i][i] = a[n - 1][i];
    N = (1 << (n - 1)) - 1;
    for(mask = 1; mask <= N; mask++)
        for(i = 0; i < n - 1; i++)
            if(dp[mask][i])
                for(j = 0; j < n - 1; j++)
                    if(a[i][j] && (!(mask & (1 << j))))
                    {
                        Mask = mask | (1 << j);
                        if(dp[Mask][j])
                            dp[Mask][j] = min(dp[Mask][j], dp[mask][i] + a[i][j]);
                        else
                            dp[Mask][j] = dp[mask][i] + a[i][j];
                    }
    sol = 1 << 30;
    for(i = 0; i < n - 1; i++)
        if(dp[N][i] && a[i][n - 1])
            sol = min(sol, dp[N][i] + a[i][n - 1]);
    sol == (1 << 30) ? printf("Nu exista solutie\n") : printf("%d\n", sol);
    return 0;
}