#include <iostream>
#include <fstream>
#include <vector>
#define maxi 18
#define INFINITY 1e9
using namespace std;
ifstream f;
ofstream g;
vector<int> V[maxi];
int cost[maxi][maxi],n,m,a,b,c,CMIN=INFINITY;
int dp[1<<maxi][maxi+2];
void INIT()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            cost[i][j]=INFINITY;
    }
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
         dp[i][j]=INFINITY;

}
inline int minim(int a,int b)
{
    return (a<b?a:b);
}
void DINAMICA_EXPONENTIALA()
{
    g.open("hamilton.out",ios::out);
    dp[1][0]=0;
    for(int mask=0;mask<(1<<n);mask++)
      for(int i=0;i<n;i++)
         if(mask&(1<<i))
            for(auto j:V[i])
                if(mask&(1<<j))
              dp[mask][i]=minim(dp[mask][i],dp[mask^(1<<i)][j]+cost[j][i]);
   for(auto j:V[0])
    CMIN=minim(CMIN,dp[(1<<n)-1][j]+cost[j][0]);
     if(CMIN==INFINITY)
        g<<"Nu exista solutie";
     else g<<CMIN;
   g.close();
   return;
}
void READ()
{
    f.open("hamilton.in",ios::in);
    f>>n>>m;
    INIT();
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        V[b].push_back(a);
        cost[a][b]=c;
    }
    f.close();
    return;
}
int main()
{
    READ();
    DINAMICA_EXPONENTIALA();
    return 0;
}