Labyrinthe de la connaissance
Problem
Attraction "Labyrinth of Knowledge" a été construit à la Summer Computer School (LCS). Le labyrinthe est composé de N salles, numérotées de 1 à N, dont certaines ont des portes entre elles. Lorsqu'une personne franchit une porte, l'indicateur de sa connaissance change d'une certaine quantité fixée pour cette porte. L'entrée du labyrinthe se trouve dans la salle 1, la sortie – dans la salle N. Chaque étudiant traverse le labyrinthe exactement une fois et entre dans l'un ou l'autre groupe d'étude en fonction de la quantité de connaissances acquises (en entrant dans le labyrinthe, cet indicateur est nul). Votre tâche est de montrer le meilleur résultat.
Saisie :
La première ligne de l'entrée contient des entiers N (1 <= N <= 2000) – nombre de pièces et M (1 <= M <= 10000) – Nombre de portes. Chacune des M lignes suivantes contient une description de la porte – les numéros des pièces d'où elle mène et auxquelles elle mène (on ne peut franchir la porte que dans un sens), ainsi qu'un nombre entier qui s'ajoute à la quantité de connaissances lors du franchissement de la porte (ce nombre ne signifie pas dépasser 10000 en modulo). Les portes peuvent mener d'une pièce à elle-même, il peut y avoir plus d'une porte entre deux pièces.
Sortie :
Afficher " :)" – si vous pouvez obtenir une quantité illimitée de connaissances, ":(" – si le labyrinthe ne peut pas être passé, et la quantité maximale de connaissances acquises autrement.
Exemples
| # |
Entrée |
Sortie |
| 1 |
2 2
1 2 3
1 2 7
7 |