#include <fstream>
#include <vector>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int MAXN=20;
const int MAXX=262150;
const int INF=100000000;
vector <int> A[MAXN];
int cost[MAXN][MAXN];
int c[MAXX][MAXN];
int n,m,sol,x,y,i,j;
int main()
{
    f>>n>>m;
    for(i=0; i<n; ++i)
        for(j=0; j<n; ++j) cost[i][j]=INF;
    for(i=1; i<=m; ++i)
    {
        f>>x>>y;
        A[y].push_back(x);
        f>>cost[x][y];

    }
 for(i=0;i< 1<<n;++i)
    for(j=0;j<n;++j) c[i][j]=INF;
 c[1][0]=0;
 for(i=0;i<1<<n;++i)
    for(j=0;j<n;++j)
    if(i&(1<<j))
    for(size_t k=0;k<A[j].size();++k)
    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(size_t i=0;i<A[0].size();++i)
    sol=min(sol,c[(1<<n)-1][A[0][i]]+cost[A[0][i]][0]);
 if(sol==INF) g<<"Nu exista solutie";
 else g<<sol;

}