#include <stdio.h>
#include <string.h>
#define N 18
#define INF 0x3F3F3F3F
#define min(a, b) a<b?a:b

int dist[N][N], dp[1<<N+1][N+1], n, m, i, j, mask, ans=INF;
int main () {
    FILE *fin=fopen("hamilton.in", "r"),
         *fout=fopen("hamilton.out", "w");
    fscanf(fin, "%d%d", &n, &m);

    memset(dist, INF, sizeof dist);
    memset(dp, INF, sizeof dp);
    dp[1][0]=0;

    for (; m; m--) {
        fscanf(fin, "%d%d", &i, &j);
        fscanf(fin, "%d", &dist[i][j]);
    }
    fclose(fin);

    int mask;
    for (mask=1; mask< 1<<n; mask++)
        for (i=0; i<n; i++)
            if (mask & (1<<i))
                for (j=0; j<n; j++)
                    if (mask & (1<<j))
                        dp[mask][i]=min(dp[mask][i], dp[mask ^ (1<<i)][j] + dist[j][i]);

    for (i=0; i<n; i++)
        ans=min(ans, dp[(1<<n)-1][i] + dist[i][0]);

    fprintf(fout, ans==INF?"Nu exista solutie":"%d", ans);
    fclose(fout);
    return 0;
}