#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
 vector <int> v[20];

 int n,m,dp[(1<<18)+3][20],cost[20][20],inf=2147000000;
 long long sol;
int main()
{ int i,j,t,x,y,b,nr;
    f>>n>>m;

    for(i=1;i<=m;i++)
    { f>>x>>y>>b;
        v[y].push_back(x);
        cost[x][y]=b;
    }
     nr=1<<n;

    for(i=0;i<nr;i++)
     for(j=0;j<n;j++)
      dp[i][j]=inf;


dp[1][0]=0;

    for(i=0;i<nr;i++)
     for(j=0;j<n;j++)
      if ((i&(1<<j)))
       {
          for(t=0;t<v[j].size();t++)
           if (i&(1<<v[j][t]) && dp[i-(1<<j)][v[j][t]]!=inf)
            dp[i][j]=min(dp[i][j],dp[i-(1<<j)][v[j][t]]+cost[v[j][t]][j]);
       }
     sol=inf;

    for(t=0;t<v[0].size();t++)
     if (dp[nr-1][v[0][t]]!=inf)
      {
         if (sol>(long long)dp[nr-1][v[0][t]]+cost[v[0][t]][0])
          sol=dp[nr-1][v[0][t]]+cost[v[0][t]][0];
      }

     if (sol!=inf) g<<sol; else g<<"Nu exista solutie";

    return 0;
}