#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define FILES freopen("hamilton.in" , "r" , stdin) , freopen("hamilton.out" , "w" , stdout)

using namespace std;

const int N = 20;

int n , m , x , y , c;
int cost[N][N] , d[(1 << 18) + 10][N];

void init()
{
    for(int j = 0 ; j < (1 << n) ; j++)
        for(int t = 0 ; t < n ; t++)
            d[j][t] = INT_MAX;

    d[1][0] = 0;
}

signed main()
{
	#ifndef ONLINE_JUDGE
		FastIO , FILES;
	#endif

    int i , j , t;

    cin >> n >> m;

    for(i = 1 ; i <= m ; i++)
    {
        cin >> x >> y >> c;
        cost[x][y] = c;
    }

    init();

    for(j = 1 ; j < (1 << n) ; j++)
        for(t = 1 ; t < n ; t++)
        {
            if((j & 1) == 0 || (j & (1 << t)) == 0)
                continue;

            for(i = 0 ; i < n ; i++)
                if(j >> i & 1)
                    if(d[j ^ (1 << t)][i] != INT_MAX && cost[i][t])
                        d[j][t] = min(d[j][t] , d[j ^ (1 << t)][i] + cost[i][t]);
        }

    int ans = INT_MAX;

    for(i = 1 ; i < n ; i++)
        if(d[(1 << n) - 1][i] != INT_MAX && cost[i][0])
            ans = min(ans , d[(1 << n) - 1][i] + cost[i][0]);

    if(ans == INT_MAX)
        cout << "Nu exista solutie";
    else cout << ans;

    return 0;
}