#include <bits/stdc++.h>

using namespace std;

int N, M, B;
int c[25][25];
int dp[300005][20];
char slv[300005][20];
int b[25];

int min0(int a, int b)
{
    if(!a)  return b;
    if(!b)  return a;
    return min(a, b);
}

int solve(int msk, int lst)
{
    if(slv[msk][lst])   return dp[msk][lst];

    int ans = 1 << 30;
    for(int x = 0; x < N; x++)
        if( (1 << x) & msk )
            if(c[x][lst])
            {
                int s = solve(msk ^ (1 << lst), x);
                if(s == -1) continue;
                ans = min(ans, s + c[x][lst]);
            }

    if(ans == (1 << 30))    ans = -1;
    slv[msk][lst] = 1;
    dp[msk][lst] = ans;
    return ans;
}

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);

    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        c[x][y] = z;
    }

    dp[1][0] = 0;
    slv[1][0] = 1;
    for(int i = 1; i < N; i++)
        dp[1 << i][i] = -1, slv[1 << i][i] = 1;

    int ans = 1 << 30;
    for(int i = 1; i < N; i++)
        if(c[i][0])
        {
            int s = solve( (1 << N) - 1, i );
            if(s == -1) continue;
            ans = min(ans, s + c[i][0]);
        }

    if(ans == (1 << 30))
    {
        printf("Nu exista solutie");
        return 0;
    }

    printf("%d\n", ans);

    return 0;
}