#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int NMAX = 18, INF = 1e9;
int cost[NMAX][NMAX], dp[(1 << NMAX)][NMAX]; ///dp[mask][nod] - costul sa ajung in masca mask si sa fiu in nodul nod
vector<int> G[NMAX];

int calc(int mask, int nod)
{
    if (dp[mask][nod] == INF)
        ///iau toate nodurile care intra in nodul meu si calculez care e cea mai ieftina varianta
    {
        for (auto vec: G[nod]) /// nu vreau ca vec sa fie 0, decat atunci cand nod este al doilea nod vizitat
        {
            if ((1 << vec) & mask) /// vecinul est in masca in mom asta
            {
                if (vec == 0 && mask != ((1 << nod) + 1))
                    continue;
                dp[mask][nod] = min(dp[mask][nod], calc(mask ^ (1 << nod), vec) + cost[vec][nod]);
            }
        }
    }
    return dp[mask][nod];
}

int main()
{
    int N, M;
    f >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cost[i][j] = INF;
        }
    }
    for (int i = 1; i <= M; i++)
    {
        int x, y, c;
        f >> x >> y >> c;
        cost[x][y] = c;
        G[y].push_back(x); /// in y intra x
    }

    for (int mask = 0; mask < (1 << N); mask++)
    {
        for (int nod = 0; nod < N; nod++)
        {
            dp[mask][nod] = INF;
        }
    }

    dp[1][0] = 0;
    int costMinim = INF;
    for (auto vec: G[0])
    {
        calc((1 << N) - 1, vec);
        costMinim = min(costMinim, dp[(1 << N) - 1][vec] + cost[vec][0]); /// vreau sa fac ciclu
    }
    if (costMinim == INF)
    {
        g << "Nu exista solutie";
    }
    g << costMinim;

}