#include <cstdio>
#include <vector>
#define MAX_N 18

using namespace std;

const int INF = (1<<30);

int dp[MAX_N+5][(1<<MAX_N)+5];
struct pereche{int nod, cost;};
vector<pereche>g[MAX_N+5];

inline int mymin(int a, int b){ return (a <b ? a : b); }

int main(){
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    int n, m, i, k, x, y, c, j, ans, mask;
    pereche p;

    scanf("%d%d", &n, &m);
    for (i=1; i<=m; i++){
        scanf("%d%d%d", &x, &y, &c);
        p.nod=x;
        p.cost=c;
        g[y].push_back(p);
    }
    for (i=0; i<n; i++)
        for (j=0; j<(1<<n); j++)
            dp[i][j]=INF;

    dp[0][1]=0;
    for (mask=0; mask<(1<<n); mask++)
        for (i=0; i<n; i++)
            if (mask&(1<<i))
                for (j=0; j<g[i].size(); j++){
                    k=g[i][j].nod;
                    if (mask&(1<<k))
                        dp[i][mask]=mymin(dp[i][mask], dp[k][mask-(1<<i)]+g[i][j].cost);
                }

    ans=INF;
    for (i=0; i<g[0].size(); i++)
        ans=mymin(ans, dp[g[0][i].nod][(1<<n)-1]+g[0][i].cost);

    if (ans<INF)
        printf("%d\n", ans);
    else
        printf("Nu exista solutie\n");

    return 0;
}