#include <fstream>
#include <vector>
#include <climits>
#include <deque>
#include <algorithm>
#include <string>

#define MOD 1999999973
#define EPSILON 0.001

using namespace std ;

ifstream cin ("hamilton.in") ;
ofstream cout ("hamilton.out") ;

long long dp[(1 << 18)][19], m[19][19] ;

vector<int> mm[19] ;

int main()
{
    int q, n ;

    cin >> n >> q ;

    for(int f = 0 ; f <= n ; f ++)
        for(int e = 0 ; e <= n ; e ++)
            m[f][e] = INT_MAX ;

    while(q --)
    {
        int a, b, c ;

        cin >> a >> b >> c ;

        m[a][b] = c ;
        mm[b].push_back(a) ; /// se poate ajunge in b din a
    }

    for(int f = 0 ; f < (1 << n) ; f ++)
        for(int e = 0 ; e <= n ; e ++)
            dp[f][e] = INT_MAX ;

    dp[1][0] = 0 ;

    for(int j = 0 ; j < (1 << n) ; j ++)
        for(int k = 0 ; k < n ; k ++)
        if(j & (1 << k)) /// verificam sa fie k in j
            for(int f = 0 ; f < mm[k].size() ; f ++)
            {
                int v = mm[k][f] ;

                if(j & (1 << v)) /// neaparat sa fie v in j
                    dp[j][k] = min(dp[j][k], dp[j ^ (1 << k)][v] + m[v][k]) ;
            }
/*
    for(int f = 0 ;  f < (1 << n) ; f ++)
    {
        for(int e = 0 ; e < n ; e ++)
            cout << dp[f][e] << " " ;

        cout << endl ;
    }
*/
    long long rez = INT_MAX ;

    for(int f = 0 ; f < mm[0].size() ; f ++)
        rez = min(rez, dp[(1 << n) - 1][mm[0][f]] + m[mm[0][f]][0]) ;

    if(rez >= INT_MAX)
    {
        cout << "Nu exista solutie" ;

        return 0 ;
    }

    cout << rez ;

    return 0 ;
}
/*
5 10
0 1 9
0 3 8
1 0 7
1 2 1
1 4 3
2 0 5
2 4 4
3 2 6
4 3 7
4 1 1
*/