#include <bits/stdc++.h>
#define cin fin
#define cout fout
#define Nmax 262159
#define oo 100000000
using namespace std;
ifstream cin ("hamiltonian.in");
ofstream cout ("hamiltonian.out");
int n,m,i,j,dp[Nmax][20],Sol,a,b,c,val;
vector<pair<int,int>>G[20];
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        G[b].push_back(make_pair(a,c));
    }
    val=1<<n;
    for(i=0;i<val;++i)
        for(j=0;j<n;j++)
            dp[i][j]=oo;
    dp[1][0]=0;
    for(i=2;i<val;i++)
        for(j=0;j<n;j++)
            for(auto k:G[j])
                dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k.first]+k.second);
    Sol=oo;
	for(auto i:G[0])
		Sol=min(Sol,dp[(1<<n)-1][i.first]+i.second);
    if(Sol==oo)
        cout<<"Nu exista solutie"<<'\n';
        else
        cout<<Sol<<'\n';
    return 0;
}