#include <bits/stdc++.h>

using namespace std;

ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

constexpr int INF = 0x3F3F3F3F;
constexpr int NMAX=18, MMAX=262144;

int n, m, x, y, c, sol, i, j, k, val, S;

int cost[NMAX][NMAX];

int dp[NMAX][MMAX];

int main()
{
    f >> n >> m;

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
            cost[i][j] = INF;
    }

    for (i = 1; i <= m; i++)
    {
        f >> x >> y >> c;

        cost[x][y] = c;
    }

    for (j = 0; j < (1 << n); j++)
    {
        for (i = 0; i < n; i++)
        {
            if (i == 0 && j == 1) dp[i][j] = 0;
            else if ((j & (-j)) == j) dp[i][j] = INF;
            else if (j == (1 << i)) dp[i][j] = INF;
            else
            {
                S = j;
                x = i;
                val = INF;
                for (k = 0; k < n; k++)
                {
                    if (k != x && (S & (1<<k)) != 0 && cost[k][x] < INF)
                    {
                        val = min(val, cost[k][x] + dp[k][S - (1<<x)]);
                    }
                }

                dp[i][j] = val;

            }
        }
    }

    sol = INF;

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

    if (sol == INF)
    {
        g <<"Nu exista solutie" << '\n';
        return 0;
    }

    g << sol << '\n';
    return 0;
}