#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int Nmax = 18;

struct muchie{
    int vecin, cost;
};
vector <muchie> vecini[Nmax];
int dp[(1<<Nmax)][Nmax], dist[Nmax][Nmax];
int main()
{
    int n, m, i, j;
    int INF = 1e9, mask;

    fin >> n >> m;
    for (i = 0; i < n; ++i )
        for ( j = 0; j < n; ++j )
            dist[i][j] = INF;


    for (i = 1; i <= m; ++i )
    {
        int a, b, c;
        fin >> a >> b >> c;
        vecini[a].push_back({b, c});
        dist[a][b] = c;
    }

    for ( mask = 1; mask < (1 << n); ++mask)
        for ( i = 0; i < n; ++i )
            dp[mask][i] = INF;

    for ( i = 0; i < n; ++i )
        dp[(1 << i)][i] = 0;
    for ( mask = 1; mask < (1 << n); ++mask )
    {
        for ( i = 0; i < n; ++i )
        {
            if ( mask & (1 << i) == 0 )
                continue;

            for ( muchie m : vecini[i])
            {
                if ( mask & (1 << m.vecin) )
                    continue;
                if ( dp[ (mask | (1 << m.vecin))][m.vecin] > dp[mask][i]+ m.cost )
                {
                    dp[ (mask | (1 << m.vecin))][m.vecin] = dp[mask][i]+ m.cost;
                    tata[ (mask | (1 << m.vecin))][m.vecin] = {mask, i};
                }
                dp[ (mask | (1 << m.vecin))][m.vecin] = min(dp[ (mask | (1 << m.vecin))][m.vecin] , dp[mask][i]+ m.cost);

            }
        }
    }
    int solution = INF, ind = -1, gasit = 0;
    for ( i = 0; i < n; ++i )
    {
        if ( dist[i][0] == INF )
            continue;
        if ( solution > dp[(1 << n) - 1][i] + dist[i][0])
        {
            gasit = 1;
            solution = dp[(1 << n) - 1][i] + dist[i][0];
            ind = i;
        }

    }
    if ( gasit == 1)
        fout << solution << endl;
    else
        fout << "Nu exista solutie\n";

    return 0 ;

}