#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int const N = 1 << 18 , M = 18 , inf = 1 << 30;
int dp [N][M];
int Cost [M][M];
vector <int> v [M];
int main()
{
    freopen ("hamilton.in" , "r" , stdin);
    freopen ("hamilton.out" , "w" , stdout);
    int n , m;
    scanf ("%d%d" , &n , &m);
    for(int i = 1 ; i <= n ; ++ i)
        for(int j = 1 ; j <= n ; ++ j)
            Cost [i][j] = inf;
    for(int i = 1 ; i <= m ; ++ i){
        int a , b  ,c;
        scanf ("%d%d%d" , &a , &b , &c);
        v [b].push_back (a);
        Cost [a][b] = c;
    }
    for(int i = 0 ; i < N ; ++ i)
        for(int j = 0 ; j < M ; ++ j)
            dp [i][j] = inf;
    dp [1][0] = 0;
    for(int i = 0 ; i < (1 << n) ; ++ i)
        for(int j = 0 ; j < n ; ++ j)
            if ((1 << j) & i)
                for(int k = 0 ; k < v [j].size () ; ++ k)
                    if ((1 << v [j][k]) & i)
                        dp [i][j] = min (dp [i][j] , dp [i ^ (1 << j)][v [j][k]] + Cost [v[j][k]][j]);
    int ans = inf;
    for(int i = 0 ; i < v [0].size () ; ++ i)
        ans = min (ans , dp [(1 << n) - 1][v [0][i]] + Cost [v [0][i]][0]);
    if (ans == inf)
        printf ("Nu exista solutie\n");
    else
        printf ("%d\n" , ans);
    return 0;

}