#include <stdio.h>
#include <vector>
#include <iostream>

#define NMAX 20
#define INF 1e9

using namespace std;

FILE *fin = fopen("hamilton.in", "r");
FILE *fout = fopen("hamilton.out", "w");

struct muchie {int x; int y; int cost;} muchii[NMAX*NMAX];

vector <int> graf[NMAX];

int n,m,i,j,k,dp[NMAX][1<<NMAX],nrsub,nod,x,y,c,ans;

int main()
{
    fscanf(fin, "%d%d", &n,&m);
    for(i=1; i<=m; ++i)
    {
        fscanf(fin, "%d%d%d", &x,&y,&c);
        muchii[i].x = x;
        muchii[i].y = y;
        muchii[i].cost = c;
        graf[y].push_back(i);
    }

    nrsub = (1<<n) - 1;
    for(i=0; i<=n-1; ++i)
        for(j=1; j<=nrsub; ++j)
            dp[i][j] = INF;
    dp[0][1] = 0; //nod 0, multimea formata din el

    for(j=1; j<=nrsub; ++j)
        for(i=0; i<=n-1; ++i)
            if((1<<i) & j)
                for(k=0; k<=graf[i].size()-1; ++k)
                {
                    nod = muchii[graf[i][k]].x;
                    if(((1<<nod) & j) and dp[nod][j^(1<<i)]+muchii[graf[i][k]].cost < dp[i][j])
                        dp[i][j] = dp[nod][j^(1<<i)]+muchii[graf[i][k]].cost;
                }

    ans = INF;
    for(i=0; i<=graf[0].size()-1; ++i)
        ans = min(ans, dp[muchii[graf[0][i]].x][nrsub] + muchii[graf[0][i]].cost);

    if(ans != INF)
        fprintf(fout, "%d", ans);
    else
        fprintf(fout, "Nu exista solutie");

    fclose(fin);
    fclose(fout);
    return 0;
}