Chemin augmentant – Épreuve régionale 2017

Énoncé¶

Joseph Marchand s'est levé de bon matin aujourd'hui, il décide d'aller faire un petit tour au parc du coin. Comme il a pas mal de temps devant lui, il cherche à parcourir le parc en empruntant un maximum de chemins.

Le parc est constitué de $N$ intersections et de $M$ chemins, empruntables dans les deux sens. Chaque chemin $i$ permet de relier exactement 2 intersections, et a pour longueur $l_i$.

Cependant, pour que l'appréciation du paysage soit meilleure à chaque nouveau chemin emprunté. Il décide de faire un tour dans lequel à chaque changement de chemin, la longueur du nouveau chemin soit strictement plus grande que celle du précédent.

Aide Joseph en déterminant le nombre maximal de chemins qu'il peut emprunter pour son tour, sachant qu'il peut entrer dans le parc à n'importe quelle intersection, et peut sortir également à n'importe laquelle.

Entrée¶

L'entrée comprendra plusieurs lignes :

• La première ligne contiendra deux entiers $N$ et $M$, le nombre d'intersections du parc et le nombre de chemins. Les intersections sont numérotées à partir de 0.
• $M$ lignes suivront. La i-ème d'entre-elles contiendra trois entiers $x_i$, $y_i$ et $l_i$, les deux intersections auxquelles est relié le i-ème chemin, ainsi que sa longueur.

Sortie¶

Vous afficherez un entier, le nombre maximal de chemins que peut emprunter Joseph pour satisfaire sa bonne appréciation du paysage.

Contraintes¶

• $1 \le N \le 10\ 000$
• $1 \le M \le \min\left (50\ 000, \displaystyle\frac{N\cdot (N - 1)}{2}\right)$
• $0 \le x_i \le N - 1$
• $0 \le y_i \le N - 1$
• $1 \le l_i \le 10\ 000$