# 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
```