#include <bits/stdc++.h>
#define newline '\n'
using namespace std;
ifstream fin("text.in");
ofstream fout("text.out");
///***********************
const int NMAX = 20, OO = 1e8;
#define to first
#define cost second
vector<pair<int, int>> graph[NMAX];
bool vis[NMAX];
int ans = OO, n, m;

void dfs(int node, int nr, int cost)
{
    vis[node] = true;
    for (auto it : graph[node])
    {
        if (!vis[it.to])
            dfs(it.to, nr + 1, cost + it.cost);
        if (!it.to && nr == n)
            ans = min(ans, cost + it.cost);
    }
    vis[node] = false;
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        graph[x].push_back(make_pair(y, c));
    }
    dfs(0, 1, 0);
    if (ans == OO)
        fout << "Nu exista solutie";
    else
        fout << ans;
    fout << newline;
    fout.close();
    return 0;
}