#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int N = 300005;
const int MAX = 2000000000;
const int M = 45;
vector <int> v[M];
int cost[M][M];
int d[M][N];

int main()
{
    int nn;
    int i, n, m, masca, afis, x, y, costul;
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d", &n, &m);
    nn = 1 << n;
    for(i = 0;i < n; ++i)
    {
        for(masca = 1;masca < nn; ++masca)
        {
            d[i][masca] = MAX;
        }
    }
    d[0][1] = 0;
    for(i = 0;i < m; ++i)
    {
        scanf("%d%d%d", &x, &y, &costul);
        v[x].push_back(y);
        cost[x][y] = costul;
    }
    for(masca = 1;masca < nn; ++masca)
    {
        for(i = 0;i < n; ++i)
        {
            if(masca & (1 << i))
            {
                for(auto it : v[i])
                {
                    if((masca & (1 << it)) == 0)
                    {
                        d[it][masca + (1 << it)] = min(d[it][masca + (1 << it)] , d[i][masca] + cost[i][it]);
                    }
                }
            }
        }
    }
    afis = MAX;
    for(i = 1; i < n; ++ i)
    {
        for(auto it: v[i])
        {
            if(it == 0)
            {
                if(cost[i][0] > 0)
                {
                    afis = min(afis, d[i][nn - 1] + cost[i][0]);
                }
                break;
            }
        }
    }
    if(afis == MAX){
        printf("Nu exista solutie");
    }
    else{
        printf("%d\n", afis);
    }
    return 0;
}