#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int INF=1e9;
const int NMAX=20;
vector <int> gr[NMAX];
int cost[NMAX][NMAX],dp[(1<<18)+5][NMAX];

void init_cost(int n)
{
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            cost[i][j]=INF;
}
void init_dp(int n)
{
    for(int masca=0; masca<(1<<n); ++masca)
        for(int last=0; last<n; ++last)
            dp[masca][last]=INF;

}

int main()
{
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	init_cost(n);
	init_dp(n);
	for(int i=1; i<=m; i++)
	{
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		gr[y].push_back(x);
		cost[x][y]=c;
	}
	dp[1][0]=0;
	for(int masca=0; masca<(1<<n); ++masca)
    {
        for(int last=0; last<n; ++last)
        {
            if(masca&(1<<last))
            {
                for(auto x: gr[last])
                    dp[masca][last]=min(dp[masca][last],dp[masca-(1<<last)][x]+cost[x][last]);
            }
        }
    }
    int rez=INF;
    for(auto x: gr[0])
        rez=min(rez,dp[(1<<n)-1][x]+cost[x][0]);
    if(rez==INF)
        printf("Nu exista solutie\n");
    else
        printf("%d\n",rez);
	return 0;
}