Problem
Afin de préparer les Olympiades d'informatique, le maire a décidé de doter toutes les écoles de la ville d'une alimentation électrique fiable. Pour ce faire, il est nécessaire de conduire une ligne électrique à partir d'une source alternative d'électricité «Maibutya” à l'une des écoles de la ville (peu importe laquelle), ainsi que pour relier certaines écoles entre elles par des lignes électriques.
Une école est considérée comme ayant une alimentation électrique fiable si elle est directement connectée à la source Maibutcha, ou à l'une de ces écoles qui dispose d'une alimentation électrique fiable.
Le coût de connexion entre certaines paires d'écoles est connu. Le maire de la ville a décidé de choisir l'un des deux systèmes d'alimentation électrique les plus économiques (le coût du système est égal à la somme des coûts de connexion des paires d'écoles).
Écrivez un programme qui calcule le coût des deux systèmes d'alimentation électrique alternatifs les plus rentables pour les écoles.
Entrée
La première ligne du fichier d'entrée contient deux nombres naturels séparés par un espace : N (3 <= N <= 100), le nombre d'écoles dans la ville, et M &ndash ; le nombre de connexions possibles entre eux. Chacune des lignes M suivantes contient trois nombres : Ai, Bi , Ci, séparés par des espaces, où Ci - coût de pose d'une ligne électrique (1 <= Ci <= 300) de l'école Ai à l'école Bi< /sub > (i=1,2,…,N).
Sortie
La ligne unique du fichier de sortie doit contenir deux nombres naturels S1 et S2 séparés par un espace &ndash ; les deux coûts de circuit les plus bas (S1 <= S2). S1=S2 si et seulement s'il existe plusieurs schémas d'alimentation électrique fiables à moindre coût.
Il est garanti qu'il existe deux schémas d'alimentation fiables différents pour les données d'entrée.
Exemples
| # |
Entrée |
Sortie |
| 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 |