noics49p2.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MAXN = 20, MAXM  = (1 << 18) + 10, INF = (1 << 30);

ll n, m;
ll mat[MAXN][MAXN], dp[MAXM][MAXN];

ll solve(ll bitmask, ll v)
{

	if(v == n - 1) return dp[bitmask][v] = 0; // Se já estou na cidade n - 1

	if(dp[bitmask][v] != -1) return dp[bitmask][v];
	
	ll ans = 0;
	
	for(ll i = 0; i < n; i++)
	{
		if(bitmask & (1 << i) or !mat[v][i]) continue; // se a cidade ja foi visitada ou não existe rota da cidade atual para ela
		
		ans = max(ans, solve((bitmask | (1 << i)), i) + mat[v][i]); // calculo o máximo entre todas as rotas possíveis
		
	}

	if(ans == 0) return dp[bitmask][v] = (-INF); // se da cidade atual não consigo ir para nenhuma outra cidade
	// então a rota é invalida e subtraio infinito para desconsidera-la

	return dp[bitmask][v] = ans;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);

	cin >> n >> m;

	while(m--)
	{
		ll a, b, w;
		cin >> a >> b >> w;
		mat[a][b] = mat[b][a] = max(mat[a][b], w); // sempre escolho a maior rota entre "a" e "b"
	}

	memset(dp, -1, sizeof(dp));

	cout << solve(1, 0) << "\n"; //sempre inicio na cidade 0 e não a visito novamente


}