///Neatza, Amerika!
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 19,
           INF = 1e9;

struct PII { ///Little known fact, in loc sa folosesc pair<,>, scriu struct-ul asta de mana *de fiecare data*
    int u, w;

    inline PII() {}
    inline PII(int _u, int _w) {
        u = _u;
        w = _w;
    }
};

vector<PII>  g[NMAX];
int         dp[NMAX][1<<NMAX];

int main(void) {
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    int n, m, a, b, c, ans;

    scanf("%d%d",&n,&m);
    while(m--) {
        scanf("%d%d%d",&a,&b,&c);
        g[b].push_back(PII(a, c));
    }

    for(int i=0; i<n; ++i)
    for(int j=0; j<(1<<n); ++j)
        dp[i][j] = INF;

    dp[0][1] = 0;

    for(int i=0; i<(1<<n); ++i)
    for(int j=0; j<n; ++j)
    if(i&(1<<j))
        for(int k=0; k<g[j].size(); ++k)
        if(i&(1<<g[j][k].u))
            dp[j][i] = min(dp[j][i], dp[g[j][k].u][i^(1<<j)] + g[j][k].w); ///Heh, ce am mai omorat cache-ul :)

    ans = INF;
    for(auto i:g[0])
        ans = min(ans, dp[i.u][(1<<n)-1] + i.w);

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

    fclose(stdin);
    fclose(stdout);
    return 0;
}