#include <bits/stdc++.h>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int MAXN = 20;
const int INF = 1000000000;
vector <int> A[MAXN], C[MAXN];
int N, M, Sol,U[MAXN];

void DFS(int nod, int nr, int cost)
{
    U[nod] = 1;

    for (int i = 0; i < A[nod].size(); ++i)
    {
        if (!U[A[nod][i]]) DFS(A[nod][i], nr+1, cost+C[nod][i]);

        if (nr == N && A[nod][i] == 0)
            Sol = min(Sol, cost+C[nod][i]);
    }

    U[nod] = 0;
}

int main()
{

    Sol = INF;
    f>> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        int x, y, c;
        f >> x >> y >> c;
        A[x].push_back(y);
        C[x].push_back(c);
    }
    DFS(0, 1, 0);
    if (Sol == INF)
        g << "Nu exista solutie" << endl;
    else
    g << Sol << endl;

    return 0;
}