Problem
A fim de se preparar para a Olimpíada de Informática, o prefeito decidiu fornecer energia elétrica confiável a todas as escolas da cidade. Para fazer isso, é necessário conduzir uma linha de energia de uma fonte alternativa de eletricidade “Maibuttya” a uma das escolas da cidade (não importa qual), bem como conectar algumas escolas entre si por linhas de energia.
Considera-se que uma escola tem uma fonte de alimentação confiável se estiver conectada diretamente à fonte Maibutcha, ou a uma dessas escolas que tenha uma fonte de alimentação confiável.
O custo de conexão entre alguns pares de escolas é conhecido. O prefeito da cidade decidiu escolher um dos dois esquemas de fornecimento de energia mais econômicos (o custo do esquema é igual à soma dos custos de conectar pares de escolas).
Escreva um programa que calcule o custo dos dois esquemas alternativos de fornecimento de energia mais econômicos para escolas.
Entrada
A primeira linha do arquivo de entrada contém dois números naturais separados por um espaço: N (3 <= N <= 100), o número de escolas na cidade e M – o número de conexões possíveis entre eles. Cada uma das seguintes linhas M contém três números: Ai, Bi , Ci, separados por espaços, onde Ci - custo de instalação de uma linha de energia (1 <= Ci <= 300) da escola Ai para a escola Bi< /sub > (i=1,2,…,N).
Saída
A única linha do arquivo de saída deve conter dois números naturais S1 e S2 separados por um espaço &ndash ; os dois custos de circuito mais baixos (S1 <= S2). S1=S2 se e somente se houver vários esquemas de fornecimento de energia confiável de menor custo.
É garantido que existem dois esquemas diferentes de fornecimento de energia confiável para os dados de entrada.
Exemplos
| # |
Entrada |
Saída |
| 1 |
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
|
110 121 |