Chantier intergalactique – Regional event 2012

Level 5

É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

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1500 milliseconds

Input/output samples

Sample input
2
1
0 1 10
Sample output
10
Sample input
2
3
0 1 5
0 1 15
1 0 8
Sample output
5
Sample input
4
5
0 1 2
0 3 5
1 2 2
1 3 3
2 3 5
Sample output
7

Submit your solution

You have to register or log in to be able to submit your solution.