//dfs - 40p
#include <fstream>
#include <cstring>
#include <vector>
#define INF 100000000
#define Nmax 20

using namespace std;

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

int n, m, min1;
int x, y, cs;
bool seen[Nmax];
vector <pair <int, int> > v[Nmax];

void dfs( int nod, int nr, int cost)
{
    seen[nod]=1;
    for ( int i = 0, l=v[nod].size(); i<l; i ++ )
    {
        if(!seen[v[nod][i].first])
        dfs(v[nod][i].first, nr+1, cost+v[nod][i].second);
        if (nr == n && v[nod][i].first == 0) min1 = min(min1, cost+v[nod][i].second);
    }
    seen[nod]=0;
}

int main()
{
    f >> n >> m;

    min1=INF;

    for ( int i = 1; i <= m; i ++ )
    {
        f >> x >> y >> cs;
        v[x].push_back({y, cs});

    }
    dfs(0, 1, 0);
    if(min1 == INF) g << "Nu exista solutie";
    else g << min1;
    return 0;
}