#include <bits/stdc++.h>
using namespace std;

const int NMAX = 18;

struct Edge {
	int neighbour, cost;
};

vector<Edge> graph[NMAX];

int cost[NMAX][NMAX];

int dp[NMAX][(1 << NMAX)];

int main() {
	int n, m;
	FILE *fin, *fout;
	fin = fopen("hamilton.in", "r");
	fout = fopen("hamilton.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cost[i][j] = 1e9;
    for(int i = 0; i < m; i++) {
        int a, b, c;
        fscanf(fin, "%d%d%d", &a, &b, &c);
        graph[a].push_back({b, c});
        cost[a][b] = c;
    }
    for(int i = 0; i < n; i++)
		for(int mask = 0; mask < (1 << n); mask++)
			dp[i][mask] = 1e9;
	dp[0][1] = 0;
    for(int mask = 1; mask < (1 << n); mask++) {
        for(int i = 0; i < n; i++) {
            if(mask & (1 << i)) {
                for(Edge x : graph[i]) {
                    if(mask & (1 << x.neighbour)) {
                        dp[x.neighbour][mask] = min(dp[x.neighbour][mask], dp[i][mask - (1 << x.neighbour)] + cost[i][x.neighbour]);
                    }
                }
            }
        }
    }
    int ans = 1e9;
    for(int i = 1; i < n; i++) {
        ans = min(ans, dp[i][(1 << n) - 1] + cost[i][0]);
    }
    if(ans == 2e9)
		fprintf(fout, "Nu exista solutie");
	else fprintf(fout, "%d", ans);
	fclose(fin);
	fclose(fout);
	return 0;
}