#include <bits/stdc++.h>

using namespace std;

FILE *F=fopen("hamilton.in", "r"), *G=fopen("hamilton.out", "w");

int n, m, x, y, z, c[262150][20], cost[20][20], lng, sol;
const int inf = 100000000;
vector<int> a[20];

int main()
{
    fscanf(F, "%d %d", &n, &m);
    for(int i = 0; i < m; ++ i)
    {
        fscanf(F, "%d %d %d ", &x, &y, &z);
        cost[x][y] = z;
        a[y].push_back(x);
    }
    lng = 1 << n;
    for(int i = 0; i < lng; ++ i)
        for(int j = 0; j < n; ++ j)
            c[i][j] = inf;
    c[1][0] = 0;
    for(int i = 1; i < lng; ++ i)
        for(int j = 0; j < n; ++ j)
            if(i & (1 << j))
            {
                for(int k = 0; k < a[j].size(); ++ k)
                    if(i & (1 << a[j][k]))
                        c[i][j] = min(c[i][j], c[i^(1 << j)][a[j][k]] + cost[a[j][k]][j]);
            }
    sol = inf;
    for(int i = 0; i < a[0].size(); ++ i)
        sol = min(sol, c[(1 << n)-1][a[0][i]] + cost[a[0][i]][0]);
    if(sol == inf)
        fprintf(G, "Nu exista solutie");
    else fprintf(G, "%d", sol);
    return 0;
}