#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#define inf INT_MAX - 10
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n, m,sol;
vector < pair <int, int> > L[19];
int U[19];

void Citire()
{  int i, x, y ,c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y>>c;
     L[x].push_back(make_pair(y,c));
    }
}
void DFS(int nod, int nr, int cost)
{ U[nod]=1;
    int i,vec;
    for(i=0;i<L[nod].size();i++)
     { vec=L[nod][i].first;
        if(U[vec]==0)
         DFS(vec,nr+1,cost+L[nod][i].second);
        if(nr==n && L[nod][i].first==0)
            sol=min(sol, cost+L[nod][i].second);
     }
   U[nod]=0;
}
int main()
{ sol=inf;
Citire();

DFS(0,1,0);
if(sol == inf) g<<"Nu exista solutie";
else g<<sol;
f.close();
g.close();
    return 0;
}