#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
int n,m,x,y,ap=3;
int cst[20][20],dp[263000][20];
vector<int>nod[20];
int get_ans(int conf,int pos)
{
    if(dp[conf][pos]!=INF)
        return dp[conf][pos];
    for(int i=0;i<nod[pos].size();i++)
    {
        if(!(conf & (1<<nod[pos][i]))) continue;
        if(nod[pos][i]==0 && conf!=(1<<pos)+1) continue;
        dp[conf][pos]=min(dp[conf][pos],get_ans(conf^(1<<pos),nod[pos][i])+cst[nod[pos][i]][pos]);
    }
    return dp[conf][pos];
}
int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin>>n>>m;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)cst[i][j]=INF;
    for(int i=0;i<(1<<n);i++) for(int j=0;j<n;j++) dp[i][j]=INF;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        fin>>cst[x][y];
        nod[y].push_back(x);
    }
    int ans=INF;
    dp[1][0]=0;
    for(int i=0;i<nod[0].size();i++)
        ans=min(ans,get_ans((1<<n)-1,nod[0][i])+cst[nod[0][i]][0]);
    if(ans==INF)
        fout<<"Nu exista solutie";
    else
        fout<<ans;
    return 0;
}