2683 - Design de Projetos

• ID: 2683
• IdBecrowd: 2683
• Tags: estruturas-dados, geometria, grafos
• Nível: 5
• Tempo Limite: 2 segundos
• Memória: 200 MB
• Categoria: Grafos
• Autor: Emílio Wuerges, UFFS

Descrição

Os engenheiros da UFFS estão estudando a possibilidade de construir túneis subterrâneos por todo o campus. Os lugares onde serão feitos as entradas, como sempre, já vieram escolhidas pelo MEC , e os túneis precisam levar diretamente de uma entrada a outra. Como a licitação já foi finalizada, estas regras acima não podem ser alteradas.

O projeto original era muito bem feito, e existia uma galeria entre cada par de entradas, que foram feitas de maneira que não se cruzassem, e o custo destas galerias já foi computado. Entretanto, com o corte de verbas, é necessário escolher apenas um subconjunto destas galerias, sem alterá-las, de maneira que exista apenas um caminho de entre cada par de entradas.

O desafio agora é saber o menor custo e o maior custo possível do projeto, pra poder encaixar no orçamento.

Entrada

A primeira linha da entrada consiste de um número 1 <= N <= 10 6  que é o número de galerias.

Cada linha seguinte, consiste de três números, 1 <= U, V <= 10 3 e 1 <= W <= 200. Que são respectivamente, entrada, saída e custo de construição da galeria.

Saída

A saída consiste de duas linhas, ambas contendo um único número.

A primeira linha deve conter o custo máximo do projeto e a segunda linha deve conter o custo mínimo do projeto.

Exemplos

Exemplo de Entrada

3

                                1 2 96

                                1 3 9

                                2 3 79

Exemplo de Saída

175

                                88