/*
	a[i][config][j] -> cost minim pentru un drum de la i la j in care exista nodurile din
  configuratia config(binara, 1 pe poz unde exista acel nod in ciclu).
	a[i][config][j] = min{ a[i][config xor 2^j][v] + cost [v][k] } unde v este un vecin al lui k care nu exista deja in configuratia config xor 2^j (sau config)
								elimin din
                                configuratie
								nodul destinatie
                                j (abia dupa adunarea
							    cost[v][k] vom avea
                                si pe j in drum
    la inceputul dinamicii, lanturile de lungime 1 vor avea cost 0.
	Dar, fiindca noi cautam cicluri, atunci nu conteaza nodul de start. => Indicele i este
inutil.

	Vom marca nodurile incepand cu 0, datorita limitei de memorie.
*/

#include <cstdio>


bool lant_lungime_1(int config)
{
	bool exista_1 = false;
	while (config > 0)
	{
		if (config%2 == 1)
		{
			if (!exista_1)
				exista_1 = true;
			else
				return false;
		}
		config >>= 1;//config /= 2;
	}
	return true;
}

bool exista_in_configuratie(int nr, int config)
{
	return config | (1<<nr) == config;
}


const int CONFIG = 1<<19 + 2; //2^(N+1)-1
const int N = 19;//19
const int INF = 2000000000;

int n;
int a[CONFIG][N];
int cost[N][N];

inline int min(int a, int b)
{
	return (a<b)?a:b;
}

void initializare_cost()
{
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cost[i][j] = INF;
}

void citire()
{
	int m,a,b,c;
	scanf("%d%d",&n);
	initializare_cost();
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		cost[a][b] = c;     //maxim un arc, nu este necesar cu min
	}
}

void initializare_dinamica()
{
	for (int config = 0; config <= 1<<n - 1; ++config)
		for (int j = 0; j < n; ++j)
			if (lant_lungime_1(config))
				a[config][j] = 0;
			else
				a[config][j] = INF;
}

void dinamica()
{
	initializare_dinamica();
	for (int config = 0; config <= 1<<n - 1; ++config)
		if (!lant_lungime_1(config))
			for (int j = 0; j < n; ++j)
				if (exista_in_configuratie(j,config))
					for (int v = 0; v < n; ++v)
						if (cost[v][j] < INF)//e vecin
							a[config][j] = min(a[config][j], a[config ^ (1<<j)][v] + cost[v][j]);
}

int main()
{
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	citire();
	dinamica();
	return 0;
}