#include<cstdio>
#include<vector>
#include<bitset>
#include<algorithm>

using namespace std;

typedef pair<int,int> PII;
const int NMAX = 18;
const int INF = (1LL<<30);

void Read(),Solve(),Print();

int N,M,Mask,Sol;
int DP[1<<NMAX][NMAX];
int Cost[NMAX][NMAX];
vector<PII> Transpose_Graph[NMAX];

int dp(int mask,int x)
{
    if(!(mask - (1<<x))) return 0;
    if(DP[mask][x]) return DP[mask][x];

    vector<PII>::iterator it;
    int y,c,p;

    for(it = Transpose_Graph[x].begin(); it != Transpose_Graph[x].end(); it++)
    {
        y = it->first;
        c = it->second;
        if(!((1<<y) & mask)) continue;
        p = dp(mask - (1<<x),y);
        if((!DP[mask][x] || DP[mask][x] > p + c) && p != INF)
            DP[mask][x] = p + c;
    }

    if(DP[mask][x]) return DP[mask][x];
    else return INF;
}

int main()
{
    Read();
    Solve();
    Print();

    return 0;
}

void Read()
{
    int x,y,c;

    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    scanf("%d%d",&N,&M);

    for(; M; --M)
    {
        scanf("%d%d%d",&x,&y,&c);
        Cost[x][y] = c;
        Transpose_Graph[y].push_back(make_pair(x,c));
    }
}

void Solve()
{
    int i;

    Mask = (1<<N)-1;

    Sol = INF;

    for(i = 1; i < N; i++)
        if(Cost[i][0]) Sol = min(Sol, dp(Mask,i) + Cost[i][0]);
}

void Print()
{
    if(Sol == INF) printf("Nu exista solutie\n");
    else printf("%d\n",Sol);
}