#include<bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;

int i,j,mask,dp[20][263005],cost[20][20],rs=INF,x,y,n,m;

int main()
{
  ifstream cin("hamilton.in");
  ofstream cout("hamilton.out");

  ios_base::sync_with_stdio(0); cin.tie(0);

  for(cin>>n>>m;m;--m) cin>>x>>y,cin>>cost[x][y];

  memset(dp,INF,sizeof(dp));

  for(dp[0][1]=0,mask=1;mask<(1<<n);++mask)
   for(i=0;i<n;++i)
   if(mask&(1<<i)) for(j=0;j<n;++j)
                   if(cost[i][j] && !(mask&(1<<j))) dp[j][mask|(1<<j)]=min(dp[j][mask|(1<<j)],dp[i][mask]+cost[i][j]);

  for(i=1;i<n;++i) if(cost[i][0]) rs=min(rs,dp[i][(1<<n)-1]+cost[i][0]);

  if(rs==INF) cout<<"Nu exista solutie\n";
  else cout<<rs<<'\n';
   
 return 0;
}