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

#define MAX_N 18
#define INF 1000000000

int noNodes, noEdges;
vector<int> graph[MAX_N];
int cost[MAX_N][MAX_N];

int dp[MAX_N][1 << MAX_N];

void addEdge(int x, int y, int c) {
    graph[x].push_back(y);
    cost[x][y] = c;
}

int main() {
    FILE *fin, *fout;
    fin = fopen("hamilton.in", "r");
    fout = fopen("hamilton.out", "w");

    int i, j, mask;
    int x, y, c;
    int minCost;

    fscanf(fin, "%d%d", &noNodes, &noEdges);

    for (i = 0; i < noNodes; ++i)
        for (j = 0; j < noNodes; ++j)
            cost[i][j] = INF;

    for (i = 0; i < noEdges; ++i) {
        fscanf(fin, "%d%d%d", &x, &y, &c);
        addEdge(x, y, c);
    }

    for (mask = 0; mask < (1 << noNodes); ++mask)
        for (i = 0; i < noNodes; ++i)
            dp[i][mask] = INF;
            
    dp[0][1 << 0] = 0;
    for (mask = 0; mask < (1 << noNodes); ++mask)
        for (i = 0; i < noNodes; ++i)
            if (mask & (1 << i))
                for (int j : graph[i])
                    if (mask & (1 << j))
                        dp[j][mask] = min(dp[j][mask], dp[i][mask - (1 << j)] + cost[i][j]);

    minCost = INF;
    for (i = 1; i < noNodes; ++i)
        minCost = min(minCost, dp[i][(1 << noNodes) - 1] + cost[i][0]);
    
    if (minCost == INF)
        fprintf(fout, "Nu exista solutie\n");
    else
        fprintf(fout, "%d\n", minCost);

    fclose(fin);
    fclose(fout);
    return 0;
}