#include <cstdio>
#include <vector>
#include <cstring>
#define INF 100000000
#define Nmax 25
#define Xmax 300000
using namespace std;

FILE *f=fopen("hamilton.in","r");
FILE *g=fopen("hamilton.out","w");

int n,m,ans;
int cost[Nmax][Nmax];
int dp[Xmax][Nmax];
vector <int> G[Nmax];

int calc(int inc, int bit, int nod)
{
    if(dp[bit][nod]==-1)
    {
        dp[bit][nod] = INF;
        for(int i=0;i<G[nod].size();i++)
        {
            if(bit & (1<<G[nod][i]))
            {
                if(G[nod][i]==inc &&((bit ^ (1<<nod)) != (1<<inc)))
                    continue;
                dp[bit][nod] = min(dp[bit][nod], calc(inc, bit ^ (1<<nod), G[nod][i]) + cost[G[nod][i]][nod]);
            }
        }
    }
    return dp[bit][nod];
}

int main()
{
    fscanf(f,"%d%d",&n,&m);

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cost[i][j] = INF;

    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fscanf(f,"%d%d%d",&x,&y,&c);

        G[y].push_back(x);
        cost[x][y] = c;
    }

    ans = INF;
    for(int i=0;i<n;i++)
    {
        memset(dp,-1,sizeof(dp));
        dp[1<<i][i]=0;
        for(int j=0;j<G[i].size();j++)
        {
            ans = min(ans,calc(i,(1<<n)-1,G[i][j])+cost[G[i][j]][i]);
        }
    }

    if(ans!=INF)
        fprintf(g,"%d\n",ans);
    else fprintf(g,"Nu exista solutie\n");

    return 0;
}