XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: banda.x, onde x deve ser c, cpp, java, js ou py

Banda

Jimmy é um garoto muito esperto que adora música. No último mês ele ganhou um campeonato de um jogo cujo objetivo é tocar guitarra. Empolgado, Jimmy decidiu montar uma banda. Para Jimmy a banda perfeita tem quatro integrantes, ele e mais três: um baterista, um baixista e um cantor.

Agora Jimmy precisa encontrar os outros integrantes da banda. Para isto ele reuniu todos os álbums que encontrou na internet e, após escutá-los diversas vezes, compilou o que ele chama de lista de entrosamento entre músicos. Nessa lista ele atribui, para cada par de músicos que já tocaram juntos, uma nota inteira de 1 a 100, que é uma medida de quão bem os músicos tocam juntos (o nível de entrosamento entre eles). Se dois músicos nunca tocaram juntos o nível de entrosamento é zero. Jimmy nunca tocou com nenhum músico da lista.

Jimmy pretende formar a sua banda a partir da lista de entrosamento entre músicos, da seguinte maneira: ele quer escolher os outros três músicos de tal forma que a soma dos níveis de entrosamento dos integrantes da banda seja a maior possível (ou seja, a soma dos níveis de entrosamento dos três pares possíveis de serem formados entre os três novos integrantes seja a maior possível). Mas a lista de entrosamento entre músicos ficou muito grande e Jimmy não está conseguindo escolher os integrantes. Por isso, Jimmy está pedindo sua ajuda.

Você deve ajudar Jimmy a montar a melhor banda possível fazendo um programa que receba uma lista contendo o nível de entrosamento para cada par de músicos que já tocaram junto, e determine os músicos que formariam a melhor banda.

Entrada

A primeira linha da entrada é formada por dois inteiros N e M, informando respectivamente o número de músicos e o número de pares de músicos que já tocaram juntos. Os músicos são identificados por números inteiros de 1 a N. Cada uma das M linhas seguintes contém três inteiros X, Y e Z, em que X e Y representa um par de músicos e Z representa o seu nível de entrosamento. Cada par de músicos que já tocou junto aparece uma única vez na entrada.

Saída

Seu programa deve imprimir na saída padrão uma única linha, contendo três números inteiros separados por espaço em branco, identificando os três outros músicos que devem compor a banda (em qualquer ordem). Se existir mais de uma melhor banda, Jimmy contenta-se com qualquer uma.

Restrições

  • 3 ≤ N ≤ 100
  • 0 ≤ M ≤ 104
  • 1 ≤ X ≤ N
  • 1 ≤ Y ≤ N
  • X ≠ Y
  • 1 ≤ Z ≤ 100

Informações sobre a pontuação

  • Em um conjunto de casos de teste que totaliza 30 pontos, N ≤ 10 e M ≤ 100.
  • Em um conjunto de casos de teste que totaliza 80 pontos, N ≤ 50 e M ≤ 2450.

Exemplos

Entrada
3 3
1 2 50
2 3 27
3 1 1
Saída
1 2 3
Entrada
58
1 2 50
1 3 50
1 4 50
2 3 50
2 5 10
3 4 50
3 5 25
4 5 20
Saída
1 3 4
Entrada

Saída

Tarefas Programação Nível Júnior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação