#include <bits/stdc++.h>
#define INF 0x7F7F7F7F
using namespace std;

int Ct[18][18];
int C[18][1<<18];
vector <int> G[18];
int N, M;

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out","w", stdout);

	/// citirea datelor
	int x, y, c;
	scanf("%d %d", &N, &M);

    memset(C, INF, sizeof(C));
    memset(Ct, INF, sizeof(Ct));

	for (int i=0; i<M; ++i) {
		scanf("%d %d %d", &x, &y, &c);
		G[x].push_back(y);
        Ct[x][y] = c;
	}

    C[0][1] = 0;
    for (int stare=1; stare < (1<<N); stare += 2) {
        for (int i=0; i<N; ++i) {
            if (C[i][stare] != INF) {
                for (int j=0; j<(int) G[i].size(); ++j) {
                    int v = G[i][j]; /// adaug muchia (i, v)
                    if ((stare & (1 << v)) == 0) {
                        int urmStare = stare + (1 << v);
                        C[v][urmStare] = min(C[v][urmStare], C[i][stare] + Ct[i][v]);
                    }
                }
            }
        }
    }

    int sol = INF;
    for (int i=0; i<N; ++i) {
        if (Ct[i][0] != INF)
            if (C[i][(1<<N)-1] != INF) {
                sol = min(sol, C[i][(1<<N)-1] + Ct[i][0]);
            }
    }

	if (sol >= INF) printf("Nu exista solutie\n");
               else printf("%d\n", sol);
	return 0;
}