Maximise ton fun ! – Qualification 2017

Énoncé¶

Joseph Marchand en a marre du boulot ! Pour se changer les idées, il décide d'aller au ski.

Après une matinée à essayer toutes les pistes, Joseph se rend compte qu'il perd parfois son temps sur des pistes qui le dépriment. Il se demande alors s'il ne peut pas optimiser son fun.

Pour cela, il dispose de la carte de la station. La station est composée de différentes plateformes, reliées par des pistes orientées : l'existence d'une piste partant de la plateforme 0 vers la plateforme 1 n'implique pas forcément l'existence d'une piste partant de la plateforme 1 vers la plateforme 0. Pour chacune d'elles, Joseph a recueilli la quantité de fun, éventuellement négative, qu'elle lui apporte.

Partant de sa plateforme initiale avec une quantité de fun nulle, il va emprunter une succession de pistes et ajouter à sa quantité de fun la dose de fun apportée par chacune de ces pistes. Sa dose de fun peut éventuellement devenir négative. De plus, comme rien ne lui interdit de repasser par une piste qu'il a déjà empruntée, il se peut, dans certains cas, qu'il puisse rendre sa quantité personnelle de fun aussi grande qu'il le désire. De plus, il est tout-à-fait possible qu'il reste sur sa plateforme initiale, sans bouger.

Votre but va être de trouver, étant donnée la liste des pistes, et sachant qu'il démarre de la première des plateformes (numérotée $0$), quel est le fun maximal que peut atteindre Joseph Marchand, ou d'indiquer s'il peut avoir autant de fun qu'il le désire.

Entrée¶

L’entrée comprendra :

• un entier $N$ représentant le nombre de plateformes ;
• un entier $M$ représentant le nombre de pistes ;
• sur les M lignes suivantes, trois entiers $x_i$, $y_i$ et $l_i$ correspondants à une piste avec une quantité de fun $l_i$ de la plateforme $x_i$ vers la plateforme $y_i$.

Sortie¶

Vous afficherez en sortie :

• La quantité de fun maximale que peut atteindre Joseph Marchand, ou «OVERDOSE DE FUN» (sans les guillemets) s'il n'y a pas de limite.

Contraintes¶

• $1 \le N \le 1\ 000$
• $1 \le M \le 1\ 000$
• $0 \le x_i \le N-1$
• $0 \le y_i \le N-1$
• $-1\ 000\ 000 \le l_i \le 1\ 000\ 000$