#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int c[262150][25];
int cost[25][25];
int n,m;
int rez(int start,int conf,int last)
{
    if(c[conf][last]==-1)
    {
        c[conf][last]=1<<30;
        for(int i=0;i<n;++i)
            if(cost[i][last] and (conf&(1<<i)))
        {
            if(i==start and ((conf^(1<<last))!=(1<<start))) continue;
                c[conf][last]=min(c[conf][last],rez(start,conf^(1<<last),i)+cost[i][last]);
        }
    }
    return c[conf][last];
}
int main()
{
f>>n>>m;
int x,y,cat;
for(int i=1;i<=m;++i)
{
    f>>x>>y>>cat;
    cost[x][y]=cat;
}
int sol=1<<30;
for(int i=0;i<n;++i)
{
    memset(c,-1,sizeof(c));
    c[1<<i][i]=0;
    for(int j=0;j<n;++j)
        if(cost[j][i])
        sol=min(sol,rez(i,(1<<n)-1,j)+cost[j][i]);
}
if(sol==1<<30)
g<<"Nu exista solutie";
else g<<sol;
    return 0;
}