#include <fstream>
#include <vector>
#define N 20
#define INF 2000000000

using namespace std;
ifstream f("hamilton.in");
ofstream  g("hamilton.out");

struct bla
{
    int ve,co;
};
vector <bla> graph[N];
int sol[1<<19][N];
int main()
{
    int n,m,x,y,c;
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        graph[x].push_back({y,c});
    }
    for(int i=0;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            sol[i][j]=INF;
    int fara;
    sol[1][0]=0;
    for(int i=2;i<(1<<n);++i)
    {
        for(int j=0;j<n;++j)
            if((i & (1<<j))!=0)
            {
                fara=i ^ (1<<j);
                for(int k=0;k<graph[j].size();++k)
                {
                    int vee=graph[j][k].ve;
                    if((i & (1<<vee))!=0)
                        sol[i][j]=min(sol[i][j],sol[fara][vee]+graph[j][k].co);
                }
            }
    }
    int mi=INF;
    for(int j=0;j<graph[0].size();++j)
        mi=min(mi,sol[(1<<n)-1][graph[0][j].ve]+graph[0][j].co);
    if(mi!=INF)
        g<<mi<<'\n';
    else
        g<<"Nu ecista solutie";
    f.close();
    g.close();
    return 0;
}