#include <fstream>
#include <vector>
#include <cstring>
#define INF 2000000001
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
vector <int> v[20];
int memo[1<<19][20],cost[20][20];
int calc(int x,int y)
{
    if(memo[x][y]==-1)
    {
    memo[x][y]=INF;
    for(int i=0;i<v[y].size();i++)
        if(x&(1<<v[y][i]))
        {
            if(v[y][i]==0 && x!=(1<<y)+1)
                continue;
            memo[x][y]=min(memo[x][y],calc(x^(1<<y),v[y][i])+cost[v[y][i]][y]);
        }
    }
    return memo[x][y];
}
int n,m,i,j,x,y,z,sol;
int main()
{
    f>>n>>m;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            cost[i][j]=INF;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        v[y].push_back(x);
        cost[x][y]=z;
    }
    memset(memo,-1,sizeof(memo));
    memo[1][0]=0;
    sol=INF;
    for(i=0;i<v[0].size();i++)
        sol=min(sol,calc((1<<n)-1,v[0][i])+cost[v[0][i]][0]);
    if(sol==INF)
        g<<"Nu exista solutie";
    else
        g<<sol;
    return 0;
}