#include<fstream>
#include<vector>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int inf=1<<29;
vector<int>v[20];
int n,m,x,y,c,i,j,ii,con;
int cost[20][20],min1;
int sol[(1<<19)][20];
int main()
{
    f>>n>>m;
    while(m)
    {
        f>>x>>y>>c;
        v[y].push_back(x);
        cost[x][y]=c;
        m--;
    }
    for(i=0;i<(1<<n);i++)
      for(j=0;j<n;j++)
        sol[i][j]=inf;
    sol[1][0]=0;
    for(i=0;i<(1<<n);i++)
      for(j=0;j<n;j++)
        if(i&(1<<j))
        {
            con=v[j].size();
            for(ii=0;ii<con;ii++)
              sol[i][j]=min(sol[i^(1<<j)][v[j][ii]]+cost[v[j][ii]][j],sol[i][j]);
        }
    min1=inf;
    con=v[0].size();
    for(i=0;i<con;i++)
      min1=min(min1,sol[(1<<n)-1][v[0][i]]+cost[v[0][i]][0]);
    if(min1!=inf)
      g<<min1;
    else
      g<<"Nu exista solutie";
    return 0;
}