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

int N,M,dp[19][1<<18],K,cost[20][20]; vector<int> graf[20];

int solve(int nod, int mask){
    if (dp[nod][mask]!=-1)
        return dp[nod][mask];

    int ans=INF,i;
    for (i=0; i<graf[nod].size(); i++)
        if (mask&(1<<graf[nod][i]) && graf[nod][i]!=0)
            ans=min(ans,solve(graf[nod][i],mask^(1<<graf[nod][i]))+cost[graf[nod][i]][nod]);

    if (mask==1 && cost[0][nod]!=-1)
        ans=solve(0,0)+cost[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(cost,-1,sizeof(cost));
    for (i=1; i<=M; i++){
        fin >> x >> y >> c;
        cost[x][y]=c;
        graf[y].push_back(x);
    }

    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    int ans=INF;
    for (i=0; i<graf[0].size(); i++)
        ans=min(ans,solve(graf[0][i],((1<<N)-1)^(1<<graf[0][i]))+cost[graf[0][i]][0]);

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

    return 0;
}