# include <cstdio>
# include <algorithm>
using namespace std;

FILE *f = freopen("hamilton.in", "r", stdin);
FILE *g = freopen("hamilton.out", "w", stdout);

const int N_MAX = 20;

struct muchie{
    int capat;
    int cost;

    muchie (int a, int b)
    {
        this -> capat = a;
        this -> cost = b;
    }
};

int vecin[N_MAX];
int bit[1<<N_MAX + 1];
int dp[1<<N_MAX + 1][N_MAX];
int dist[N_MAX][N_MAX];

int n, m;

void read()
{
    scanf("%d %d", &n, &m);

    for (int i=1; i<=m; i++)
    {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);

        dist[x][y] = z;

        vecin[y] ^= (1 <<x);
    }

    for (int i=0; i<n; i++)
        bit[1 << i] = i;
}

void solve()
{
    int limit = 1<<(n-1);

    for (int mask= 0; mask < limit; mask ++)
    {
        for (int x=0; x<n; x++)
        {
            dp[mask][x] = 1e9;
        }
    }

    dp[0][n-1] = 0;

    for (int mask = 1; mask < limit; mask ++)
    {
        int temp_mask = mask;

        while (temp_mask)
        {
            int new_mask = temp_mask & (temp_mask - 1); /// eliminam ultimul bit
            int last_bit = temp_mask ^ new_mask; /// ultimul bit
            int v = bit[last_bit];

            temp_mask = new_mask;

            int config = vecin[v];

            while (config)
            {
                int new_config = config & (config - 1);
                int last_bit2 = config ^ new_config;
                int u = bit[last_bit2];

                config = new_config;

                if (dp[mask][v] > dp[mask ^ (1<<v)][u] + dist[u][v])
                    dp[mask][v] = dp[mask ^ (1<<v)][u] + dist[u][v];
            }
        }
    }

    int sol = 1e9;

    for (int i=0; i<n-1; i++)
    {
        if (dist[i][n-1])
            sol = min(sol, dp[limit - 1][i] + dist[i][n-1]);
    }

    if (sol != 1e9)
        printf("%d\n", sol);
    else
        printf("Nu exista solutie");
}

int main()
{
    read();
    solve();
    return 0;
}