#include <bits/stdc++.h>

using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int Hamilton(const vector<vector<int>>& cost)
{
	int n = cost.size();
	vector<vector<int>> dp((1 << n),vector<int>(n, (1<<29)));
	dp[1][0] = 0;
	for (int mask=2;mask<dp.size();mask++)
    {
		if((mask&1)==0)
            continue;
		for (int i=0;i<n;i++)
		{
			if((mask&(1 << i))==0)
                continue;
			for (int j=0;j<n;j++)
			{
				if((mask&(1 << j))==0)
                    continue;
				dp[mask][i] = min(dp[mask ^ (1 << i)][j] + cost[j][i], dp[mask][i]);
			}
		}
	}
	int cnt=(1<<29);
	for (int i=0;i<n;i++)
		cnt=min(cnt, dp[(1 << n) - 1][i] + cost[i][0]);
	if(cnt==(1<<29))
        return -1;
    else
        return cnt;
}

int main()
{
	int n,m;
	in>>n>>m;
	vector<vector<int>> cost(n,vector<int>(n,(1<<29)));
	for (int i=0;i<m;i++)
    {
		int a, b, c;
		in>>a>>b>>c;
		cost[a][b]=c;
	}
	int cnt=Hamilton(cost);
	if (cnt == -1)
		out<<"Nu exista solutie\n";
	else
		out<<cnt<<"\n";
	return 0;
}