Das Labyrinth des Wissens
Problem
In der Sommerschule (LKS) wurde eine Attraktion "Labyrinth des Wissens" gebaut. Das Labyrinth besteht aus N Räumen, die von 1 bis N nummeriert sind, von denen einige Türen haben. Wenn eine Person durch eine Tür geht, ändert sich die Kennziffer seines Wissens um einen bestimmten Wert, der für eine bestimmte Tür festgelegt ist. Der Eingang zum Labyrinth befindet sich in Raum 1, der Ausgang in Raum N. Jeder Schüler durchläuft das Labyrinth genau einmal und trifft abhängig von der Anzahl der erworbenen Kenntnisse in eine Lerngruppe (beim Betreten des Labyrinths ist dieser Wert Null). Ihre Aufgabe ist es, das beste Ergebnis zu zeigen.
Eingabe:
Die erste Zeile der Eingabe enthält ganze Zahlen N (1 <= N <= 2000) – Anzahl der Räume und M (1 <= M <= 10000) – Anzahl der Türen. Jede der folgenden M Zeilen enthält eine Beschreibung der Tür, aus der sie führt und zu der sie führt (man kann nur in eine Richtung durch die Tür gehen), sowie eine ganze Zahl, die der Menge an Wissen hinzugefügt wird, wenn sie durch die Tür gehen (diese Zahl ist modular nicht größer als 10.000). Türen können von einem Raum selbst hinein führen, es kann mehr als eine Tür zwischen zwei Räumen geben.
Ausgabe:
Zeige ":)" – wenn du unbegrenzt viel Wissen erhalten kannst, ":(" – wenn das Labyrinth nicht passieren kann und die maximale Menge an Wissen, die du sonst gesammelt hast, nicht erreicht werden kann.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
2 2
1 2 3
1 2 7
|
7 |