#include <cstdio>
#include <vector>
#include <queue>
#define Nmax 20
#define INF 2000000000

using namespace std;

struct Edge
{
    int nod,cost;
};
struct el
{
    int nod,stare;
};
vector <Edge> L[Nmax];
queue <el> Q;
int dp[(1<<20)][20],N;

inline void Dinamic()
{
    el w,w1;
    vector <Edge>:: iterator it;
    w.nod=1; w.stare=1; Q.push(w);
    while(!Q.empty())
    {
        w=Q.front(); Q.pop();
        for(it=L[w.nod].begin();it!=L[w.nod].end();++it)
        {
            int aux=((1<<(it->nod-1))&w.stare);
            if(!aux || (aux && it->nod==1 && w.stare==(1<<N)-1))
            {
                if(dp[(w.stare|(1<<(it->nod-1)))][it->nod]>dp[w.stare][w.nod]+it->cost)
                {
                    dp[(w.stare|(1<<(it->nod-1)))][it->nod]=dp[w.stare][w.nod]+it->cost;
                    w1.nod=it->nod; w1.stare=(w.stare|(1<<(it->nod-1)));
                    Q.push(w1);
                }
            }
        }
    }
}

int main()
{
    int M,a,b,c,i,j;
    Edge w;
    freopen ("hamilton.in","r",stdin);
    freopen ("hamilton.out","w",stdout);
    scanf("%d%d", &N,&M);
    while(M--)
    {
        scanf("%d%d%d", &a,&b,&c);
        ++a; ++b;
        w.nod=b; w.cost=c;
        L[a].push_back(w);
    }
    for(i=1;i<(1<<N);++i)
        for(j=1;j<=N;++j)
            dp[i][j]=INF;
    dp[1][1]=0;
    Dinamic();
    if(dp[(1<<N)-1][1]!=INF)
        printf("%d\n", dp[(1<<N)-1][1]);
    else
        printf("Nu exista solutie\n");
    return 0;
}