#include <bits/stdc++.h>
#define inf 999999999
#define nmax 19
using namespace std;
vector<int>g[nmax];
int dp[1<<nmax][nmax], cost[nmax][nmax];
int n, m;
int x, y, ct, af;
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=0;i<n;++i)
        for (int j=0;j<n;++j)
            cost[i][j] = inf;
    for (int i=1;i<=m;++i)
    {
        scanf("%d %d %d",&x,&y,&ct);
        cost[x][y] = ct;
        g[y].push_back(x);
    }
    // parcurg toate configuratiile posibile 1<<n - 1 posibile, si initializez dp-ul cu inf
    for (int i=0;i<(1<<n);++i)
        for (int j=0;j<n;++j)
            dp[i][j] = inf;
    dp[1][0] = 0;
    for (int i=0;i<(1<<n);++i)
        for (int j=0;j<n;++j)
    {
        if (!(i&(1<<j))) continue;
        for (auto nd : g[j])
        {
            if (cost[nd][j]==inf) continue;
            if (!(i & (1<<nd))) continue; // nodul curent nu apare vizitat in configuratia actuala
            dp[i][j] = min(dp[i][j],dp[i^(1<<j)][nd] + cost[nd][j]);
        }
    }
    af = inf;
    for (auto nd : g[0])
    {
        if (cost[nd][0] == inf) continue;
        af = min(af, dp[(1<<n)-1][nd] + cost[nd][0]); // costul minim pt configuratia completa ce se termina in nodul nd + costul de la nd la nodul 0
    }
    if (af == inf)
        printf("Nu exista solutie");
    else
        printf("%d\n",af);
    fclose(stdin);
    fclose(stdout);
    return 0;
}