#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in");

ofstream fout("hamilton.out");

int adi[20][20];

int dp[20][(1 << 17) + 4]; // dp[nod][conf] = costul minim ca sa se ajunga in nodul nod trecand exact prin

// nodurile cu 1 din conf

int N, M;

int main()
{
    fin >> N >> M;
    int a, b, c;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            adi[i][j] = INT_MAX;
        }
    }
    for (int i = 1; i <= M; i++)
    {
        fin >> a >> b >> c;
        adi[a][b] = c;
    }
    for (int conf = 1; conf < (1 << (N - 1)); conf++)
    {
        for (int i = 0; i < N; i++)
        {
            dp[i][conf] = INT_MAX;
        }
    }
    for (int i = 0; i < N; i++)
    {
        dp[i][(1 << (i - 1))] = adi[0][i];
    }
    dp[0][0] = 0;
    for (int conf = 1; conf < (1 << (N - 1)); conf++)
    {
        for (int nodnou = 1; nodnou < N; nodnou++)
        {

            if ((conf & (1 << (nodnou - 1))) == 0)
            {

                for (int nodvechi = 1; nodvechi < N; nodvechi++)
                {

                    if ((conf & (1 << (nodvechi - 1))) != 0 && adi[nodvechi][nodnou] < INT_MAX)
                    {
                        dp[nodnou][conf ^ (1 << (nodnou - 1))] = min(dp[nodnou][conf ^ (1 << (nodnou - 1))], dp[nodvechi][conf] + adi[nodvechi][nodnou]);
                    }
                }
            }
        }
    }
    int rez = INT_MAX;
    for (int i = 1; i < N; i++)
    {
        rez = min(rez, dp[i][(1 << (N - 1)) - 1] + adi[i][0]);
    }
    if (rez == INT_MAX)
    {

        fout << "Nu exista solutie";
    }
    else
    {
        fout << rez;
    }
    return 0;
}