#include <bits/stdc++.h>
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
FILE *fin  = freopen("hamilton.in", "r", stdin);
FILE *fout = freopen("hamilton.out", "w", stdout);

using namespace std;
const int Nmax = 18;
const int inf = 1e9+2;
int n, m;
int sol = inf;
vector <pii> G[Nmax+2];
bitset <Nmax+2> seen;
int dp[1<<Nmax+2][Nmax];

void Read(){
    int u, v, c;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++ i){
        scanf("%d%d%d", &u, &v, &c);
        G[v].push_back(mp(u, c));
    }
}

void Dfs(int node, int nr, int cost){
    seen.set(node);
    for(pii son : G[node]){
        if(!seen.test(son.f))
            Dfs(son.f, nr+1, cost + son.s);
        if(nr == n && son.f == 0) // back to where we started
            sol = min(sol, cost+son.s);
    }
    seen.reset(node);
}

void Dp(){
    for(int i = 0; i < (1<<n); ++ i)
        for(int j = 0; j < n; ++ j)
            if(i != (1 << j))
                dp[i][j] = inf;
    dp[1][0] = 0;

    for(int state = 0; state < (1<<n); ++ state)
        for(int node = 0; node < n; ++ node)
            if(state & (1 << node))
                for(pii son : G[node])
                    if(state & (1 << son.f))
                        dp[state][node] = min(dp[state][node],
                        dp[state^(1<<node)][son.f] + son.s);
    for(pii node : G[0])
        sol = min(sol, dp[(1<<n)-1][node.f]+node.s);
}

void Solve(){
    //if(n < 9)
        //Dfs(0, 1, 0);
    Dp();
}

void Write(){
    if(sol == inf)
        printf("Nu exista solutie");
    else printf("%d\n", sol);
}

int main(){
    Read();
    Solve();
    Write();
    return 0;
}