/**
  *  Worg
  */
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
FILE *fin = freopen("hamilton.in", "r", stdin);
FILE *fout = freopen("hamilton.out", "w", stdout);

const int MAX_N = 18,
          MAX_INF = 0x3fffffff;

int cost[MAX_N][MAX_N], dp[1 << MAX_N][MAX_N];
int vecini[MAX_N];
int n, m;
char bit[1 << MAX_N];

void readData() {

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {

        int u, v, c; scanf("%d%d%d", &u, &v, &c);
        cost[u][v] = c;
        vecini[v] ^= (1 << u);
    }
    for(int i = 0; i < n; ++i)
        bit[1 << i] = i;
}

void runDp() {

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

    for(int mask = 1; mask < limit; ++mask) {

        int tmpMask = mask;
     //   printf("%d:\n", mask);
        while(tmpMask) {

            int newMask = tmpMask & (tmpMask - 1);
            int v = bit[newMask ^ tmpMask]; /* calculam dp[mask][v] */
            tmpMask = newMask;
          //  printf("%d: ", v);

           // printf("%d %d;", mask, vecini[v]);
            int config = vecini[v];
            while(config) {

                int newConfig = config & (config - 1);
                int u = bit[config ^ newConfig];
             //   printf("%d ", u);
                config = newConfig;

                dp[mask][v] = min(dp[mask][v], dp[mask ^ (1 << v)][u] + cost[u][v]);
            }
          //  printf("\n");
        }
      //  printf("---------\n");
    }

  /*  printf("\n\n\n");
    for(int i = 1; i < limit; ++i) {

        printf("%d:\n", i);
        for(int j = 0; j < n - 1; ++j)
            printf("%d %d\n", j, dp[i][j]);
        printf("-------------\n");*/

    int sol = MAX_INF;
    for(int i = 0; i < n - 1; ++i)
        if(cost[i][n - 1])
            sol = min(sol, dp[limit - 1][i] + cost[i][n - 1]);

    if(sol == MAX_INF)
        printf("Nu exista solutie");
    else
        printf("%d\n", sol);
}

int main() {

    readData();
    runDp();
    return 0;
}