Chantier intergalactique – Épreuve régionale 2012

Énoncé¶

Joseph Marchand vient d'être embauché dans une entreprise de travaux publics. Il est appelé sur un chantier de rénovation de routes intergalactiques. La rénovation doit permettre de joindre toutes les planètes du système solaire via ces nouvelles routes spatiales.

Évidemment, la rénovation d'une route coûte cher, on veut donc en rénover le moins possible. Les routes rénovées devront interconnecter toutes les planètes.

Entrée¶

• Sur la première ligne, un nombre P de planètes.
• Sur la seconde ligne, un nombre R de routes spatiales existantes.
• Sur les R lignes suivantes, un triplet (V1, V2, L) représentant une route spatiale entre P1 et P2 de longueur L kilomètres.

P1 et P2 sont les numéros des villes, de 0 à (P - 1) inclus.

Sortie¶

Renvoyez le nombre de kilomètres de routes spatiales à rénover au minimum pour que les planètes soient toutes joignables par ces routes.

Le guide galactique du voyageur vous rappelle que les autorisations nécessaires à la construction de nouvelles routes demandent l'approbation d'un superviseur vogon, ce qui très (trop) long à obtenir. Vous ne pourrez donc que rénover les anciennes routes.

Enfin, le guide vous précise que les routes spatiales sont à double sens !

Contraintes¶

• 1 <= P <= 200
• 1 <= R <= 40 000
• 1 <= L <= 42
• 0 <= P1 < V
• 0 <= P2 < V