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

using namespace std;

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

const int MAXN = 20;
const int inf = 100000000;

int N, M, Sol;
int Cost[MAXN][MAXN];
int C[262160][MAXN];
vector <int> A[MAXN];

int main()
{
    in >> N >> M;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            Cost[i][j] = inf;     /// Intializez toate costurile cu infINIT

    for (int i = 1; i <= M; ++i) /// Citesc nodurile, muschiile si costul.
    {
        int x, y;
        in >> x >> y;
        A[y].push_back(x);
        in >> Cost[x][y];
    }
    for (int i = 0; i < 1 << N; ++i)
        for (int j = 0; j < N; ++j)
            C[i][j] = inf;    /// Initializez matricea de pd cu inf

    C[1][0] = 0;  /// Costul de a ajunge in nodul 0 din nodul 0

    for (int i = 0; i < 1 << N; ++i)  /// Toate configuratiile
        for (int j = 0; j < N; ++j)   /// Care se termina in J
        {
            if ((i & (1<<j))!=0)   /// Daca exista in configuratie
            {
                for (long long k = 0; k < A[j].size(); ++k) /// Verific toate nodurile legate
                    if (i & (1<<A[j][k]))
                        C[i][j] = min(C[i][j], C[i^(1<<j)][ A[j][k] ]+Cost[ A[j][k] ][j]);
            }
        }
    Sol = inf;
    for (long long i = 0; i < A[0].size(); ++i) /// solutia e minimul dintre toate ciclurile complete care se termina in i;
        Sol = min(Sol, C[(1<<N) - 1][ A[0][i] ] + Cost[ A[0][i] ][0]);

    if (Sol == inf)
        out << "Nu exista solutie" << endl;
    else
        out << Sol << endl;
    return 0;
}