#include <iostream>
#include <fstream>
#include <cstring>
#define INF (1<<30)
using namespace std;

int N,M,dp[19][1<<18],nod[19],K,graf[20][20]; bool v[19][1<<18];

int solve(int nod, int mask){
    if (v[nod][mask])
        return dp[nod][mask];

    int ans=INF,cnt=0;
    v[nod][mask]=1;
    for (int i=1; i<N; i++)
        if (mask&(1<<i)){
            if (graf[i][nod]!=-1)
                ans=min(ans,solve(i,mask^(1<<i))+graf[i][nod]);
            cnt++;
        }

    if (!cnt && graf[0][nod]!=-1)
        ans=solve(0,0)+graf[0][nod];

    return dp[nod][mask]=ans;
}

int main(){
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin >> N >> M;

    int i,x,y,c;
    memset(graf,-1,sizeof(graf));
    for (i=1; i<=M; i++){
        fin >> x >> y >> c;
        graf[x][y]=c;
        if (y==0) nod[++K]=x;
    }

    v[0][0]=1;
    int ans=INF;
    for (i=1; i<=K; i++)
        ans=min(ans,solve(nod[i],((1<<N)-1)^(1<<nod[i]))+graf[nod[i]][0]);

    if (ans==INF)
        fout << "Nu exista solutie\n";
    else
        fout << ans << "\n";

    return 0;
}