#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in");

ofstream fout("hamilton.out");

int adi[18][18];

int dp[18][(1 << 17)]; // 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++)
    {
        if (adi[i][0] < INT_MAX)
        {
            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;
}