# include <cstdio>
# include <algorithm>

using namespace std;

# define FIN "hamilton.in"
# define FOUT "hamilton.out"

# define inf 0x3f3f3f3f
# define MAX_N 19
# define MAX_M MAX_N * MAX_N
# define MAX_L 1 << 18

# define ff first
# define sf second.first
# define ss second.second

int N, M, i, j, _i, sol;
int D[MAX_L][MAX_N];
pair <int, pair <int, int> > G[MAX_M];

     inline int min(int A, int B) {
         return A < B ? A : B;
     }

     int main() {
         freopen(FIN, "r", stdin);
         freopen(FOUT, "w", stdout);
         
         scanf("%d%d", &N, &M);
         for (i = 1; i <= M; ++i)
            scanf("%d%d%d", &G[i].ff, &G[i].sf, &G[i].ss);
            
         memset(D, inf, sizeof(D));
         D[1][0] = 0;
            
         int BND = 1 << N;
         for (i = 1; i < BND; ++i) {
             if (!(i & 1)) continue;
             for (j = 1; j <= M; ++j)
                if (((1 << G[j].ff) & i) && ((1 << G[j].sf) & i) && G[j].sf)
                   D[i][G[j].sf] = min(D[i][G[j].sf], D[i - (1 << G[j].sf)][G[j].ff] + G[j].ss);
         }
         
         sol = inf;
         for (i = 1; i <= M; ++i)
            if (!G[i].sf) sol = min(sol, D[BND - 1][G[i].ff] + G[i].ss);
         
         sol == inf ? printf("Nu exista solutie\n") : printf("%d\n", sol);
         
         return 0;
     }