#include <fstream>
#include <vector>

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
vector<int> V[20];
int dp[300000][20],c[20][20],n,m,sol;
int main()
{
    int a,b,i,j;
    f>>n>>m;
    for(i=0;i<n;i++)
     for(j=0;j<n;j++)
    c[i][j]=100000000;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        f>>c[a][b];
        V[b].push_back(a);
    }

    for(i=0;i< 1<<n;i++)
     for(j=0;j<n;j++)
      dp[i][j]=100000000;
    dp[1][0]=0;

    for(i=0;i< 1<<n;i++)
    for(j=0;j<n;j++)
      if(i & (1<<j))
        for (size_t ii=0;ii<V[j].size();ii++)
          if (i&(1<<V[j][ii]))
            dp[i][j]=min(dp[i][j],dp[i^(1<<j)][V[j][ii]]+c[V[j][ii]][j]);

    sol=100000000;
    for (size_t i=0;i<V[0].size();i++)
     sol=min(sol,dp[(1<<n)-1][V[0][i]]+c[V[0][i]][0]);
    if (sol==100000000) g<<"Nu exista solutie";
    else g<<sol;
    return 0;
}