#include <bits/stdc++.h>
using namespace std;
const int NMAX = 20;
const int INF = 100000000;
vector<int>a[NMAX + 5];
int cost[NMAX + 5][NMAX + 5], dp[(1 << NMAX) + 5][NMAX + 5];
int main(){
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    int n, m, x, y, c, i, j, v, ans = INF;
    scanf("%d%d", &n, &m);
    for(i = 0; i < m; i ++){
        scanf("%d%d%d", &x, &y, &c);
        a[y].push_back(x);
        cost[x][y] = c;
    }
    for(i = 0;  i < (1 << n); i ++)
        for(j = 0; j < n; j ++)
            dp[i][j] = INF;
    dp[1][0] = 0;
    for(i = 0; i < (1 << n); i ++)
        for(j = 0; j < n; j ++)
            if((1 << j) & i)
                for(v = 0; v < a [j].size(); v ++)
                    if ((1 << a[j][v]) & i)
                        dp[i][j] = min(dp[i][j], dp[(1 << j) ^ i][a[j][v]] + cost[a[j][v]][j]);
    for(i = 0; i < a[0].size(); i ++)
         ans = min(ans, dp[(1 << n) - 1][a[0][i]] + cost[a[0][i]][0]);
    if(ans == INF)
        printf("Nu exista solutie\n");
    else
        printf("%d\n", ans);
    return 0;
}