#include <bits/stdc++.h>

using namespace std;

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

constexpr int INF = 0x3f3f3f3f;
constexpr int NMAX=19, MMAX=262146;

vector <int> G[NMAX];

int n, m, x, y, c;

int cost[NMAX][NMAX];

int dp[MMAX][NMAX];

inline void citire ()
{
    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)
    {
        f >> x >> y >> c;

        G[y].push_back(x);

        cost[x][y] = c;
    }

    for (int i = 0; i < MMAX; ++i)
    {
        for (int j = 0; j < NMAX; ++j)
        {
            dp[i][j] = -1;
        }
    }

    dp[1][0] = 0;
}

inline int functie (int S, int x)
{
    if (dp[S][x] == -1)
    {
        dp[S][x] = INF;

        for (int k = 0; k < G[x].size(); ++k)
            if (S & (1<<G[x][k]))
                dp[S][x] = min(dp[S][x], cost[G[x][k]][x] + functie(S^(1<<x), G[x][k]));
    }

    return dp[S][x];
}

inline void solve()
{
    int sol = INF;

    for (int i = 0; i < G[0].size(); ++i)
        sol = min(sol, functie((1<<n) - 1, G[0][i]) + cost[G[0][i]][0]);

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

        return;
    }

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

int main()
{
    f.tie(NULL);

    citire();

    solve();

    return 0;
}