#include <cstdio>
#include <vector>
#include <cstring>

#define pb push_back
#define FILEIN "hamilton.in"
#define FILEOUT "hamilton.out"
#define  NMAX 19
#define _NMAX 262144
#define INF 0x3f3f3f3f

using namespace std;

int n, m, rez;
int Cost[NMAX][NMAX];
int C[_NMAX][NMAX];
vector<int> A[NMAX];

inline int min(int a, int b)
{
    return a < b ? a : b;
}

int main()
{
    int i, j, k,x,y;
    freopen(FILEIN,"r",stdin);
    freopen(FILEOUT,"w", stdout);
    scanf("%d %d", &n, &m);
    memset(C, INF,sizeof(C));
    memset(Cost,INF,sizeof(Cost));
    for ( i = 1; i <= m; i++)
    {
        scanf("%d %d", &x, &y);
        A[y].pb(x), scanf("%d", &Cost[x][y]);
    }
    C[1][0] = 0;
    for ( i = 1; i < 1<<n; i++)
        for ( j = 0; j < n; j++)
            if( i & (1<<j))
                for ( k = 0; k < A[j].size(); k++)
                    if( i & (1<<A[j][k]))
                        C[i][j] = min(C[i][j], C[i^(1<<j)][A[j][k]] + Cost[A[j][k]][j]);

    rez = INF;
    for ( i = 0; i < A[0].size(); i++)
        rez = min(rez,C[(1<<n)-1][A[0][i]] +Cost[A[0][i]][0]);
    if ( rez == INF)
        printf("Nu exista solutie\n");
    else
        printf("%d\n",rez);
    return 0;
}