#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
int n,m,a,b,c;
int dp[(1<<18)][19],w[19][19];
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	cin>>a>>b>>c;
    	w[a][b]=c;
    }
    for(int i=1;i<(1<<n);i++)
    {
    	for(int j=0;j<n;j++)
    		dp[i][j]=2e9;
    }
 	dp[1][0]=0;   
    for(int mask=3;mask<(1<<n);mask++)
    {
    	for(int r=0;r<n;r++)
    	{
    		if(!(mask&(1<<r))) continue;
    		for(int l=0;l<n;l++)
    		{
    			if(!(mask&(1<<l) && w[l][r])) continue;

    			dp[mask][r]=min(dp[mask][r],dp[mask^(1<<r)][l]+w[l][r]);
    		}
    	}
    }
    int ans=2e9;
    for(int i=0;i<n;i++)
    {
    	if(!w[i][0]) continue;
    	ans=min(ans,dp[(1<<n)-1][i]+w[i][0]);
    }
    if(ans==2e9)
    	cout<<"Nu exista solutie";
    else
    	cout<<ans;
    return 0;
}