#include<fstream>
#include<vector>
#include<cstring>
#define pb push_back
#define INF 999999999
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,j,i,sol,x,y,c[20][20],a[280000][20];
vector<int>v[20];
inline int rez(int config,int x)
{
    if(a[config][x]!=-1)
    return a[config][x];
    a[config][x]=INF;
    for(int i=0;i<v[x].size();++i)
    if(config&(1<<v[x][i]))
    {
        if(v[x][i]==0&&config!=((1<<x)+1))
        continue;
        a[config][x]=min(a[config][x],rez(config^(1<<x),v[x][i])+c[v[x][i]][x]);
    }
    return a[config][x];
}
int main()
{
    f>>n>>m;
    for(i=0;i<n;++i)
    for(j=0;j<n;++j)
    c[i][j]=INF;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        f>>c[x][y];
        v[y].pb(x);
    }
    memset(a,-1,sizeof(a));
    sol=INF;
    a[1][0]=0;
    for(i=0;i<v[0].size();++i)
    sol=min(sol,rez((1<<n)-1,v[0][i])+c[v[0][i]][0]);
    if(sol==INF)
    g<<"Nu exista solutie\n";
    else
    g<<sol<<'\n';
    return 0;
}