#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
const int N = 1e5 + 5, INF = 1e9;

int n, m, dp[20][(1ll << 19)], grid[20][20];


int main()
{
    ios_base::sync_with_stdio(0);
    fin>>n>>m;
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		fin >> x >> y >> c;
		grid[x][y] = c;
	}
	/// dp[i][mask] = lungimea minima a unui lant hamiltonian care se termina in nodul i si contine masca de noduri
	/// dp[i][mask] = min(dp[i][mask], dp[j][mask ^ (1ll << i)] + muchia(j, i));
	for (int i = 0; i < n; i++) {
		for (int mask = 0; mask < (1ll << n); mask++) {
			dp[i][mask] = INF;
		}
	}
    dp[0][1]=0;
    for(int bitmask = 1; bitmask<(1<<n); bitmask++)
    {
        for(i=0;i<n;i++) // ultimul nod pe care il adaugam la un dp anterior pentru a obtine dp[masca]
        {
            if(bitmask & (1<<i)) // daca nodul i apartine drumului specificat de masca
            {
                for(j=0;j<n;j++) // ultimul dp de la care puteam ajunge
                {
                    if(i!=j && graf[i][j] && (bitmask & (1<<j)) && dp[i][bitmask]>dp[j][bitmask ^ (1<<i)] + graf[i][j])
                    {
                        dp[i][bitmask] = dp[j][bitmask ^ (1<<i)] + graf[i][j];
                    }
                }
            }
        }
    }
	int ans = INF;
	for (int i = 1; i < n; i++) {
		if (grid[i][0])
			ans = min(ans, dp[i][(1ll << n) - 1] + grid[i][0]);
	}
	if (ans != INF)
		fout << ans;
	else
		fout << "Nu exista solutie";



    return 0;
}