#include <cstdio>
#include <vector>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;
int n, m, dp[1<<18][18], c[19][19];
vector<int> v[19];
int main(){
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    scanf("%d %d\n", &n, &m);
    for(int i = 0; i < n; ++i)
        memset(c[i], inf, sizeof(c[i]));
    for(int i = 1; i <= m; ++i){
        int x, y;
        scanf("%d %d ", &x, &y);
        v[y].push_back(x);
        scanf("%d\n", &c[x][y]);
    }
    for(int i = 0; i < (1<<n); ++i)
        memset(dp[i], inf, sizeof(dp[i]));
    dp[1][0] = 0;
    for(int conf = 0; conf <= (1<<n); ++conf)
        for(int i = 0; i < n; ++i)
            if(conf & (1<<i))
                for(int j = 0; j < v[i].size(); ++j)
                    if(conf & (1<<v[i][j]))
                        dp[conf][i] = min(dp[conf - (1<<i)][v[i][j]] + c[v[i][j]][i], dp[conf][i]);
    int sol = inf;
    for(int i = 0; i < v[0].size(); ++i)
        sol = min(sol, dp[(1<<n) - 1][v[0][i]] + c[v[0][i]][0]);
    if(sol == inf)
        printf("Nu exista solutie\n");
    else printf("%d\n", sol);
    return 0;
}