Problem
La atracción "Laberinto del conocimiento" se construyó en la Escuela de informática de verano (LCS). El laberinto consta de N habitaciones, numeradas del 1 al N, algunas de las cuales tienen puertas entre ellas. Cuando una persona pasa por una puerta, el indicador de su conocimiento cambia en una cierta cantidad fijada para esta puerta. La entrada al laberinto está en la habitación 1, la salida – en la sala N. Cada estudiante atraviesa el laberinto exactamente una vez y se integra en uno u otro grupo de estudio según la cantidad de conocimiento adquirido (al ingresar al laberinto, este indicador es cero). Tu tarea es mostrar el mejor resultado.
Entrada:
La primera línea de la entrada contiene números enteros N (1 <= N <= 2000) – número de habitaciones y M (1 <= M <= 10000) – Número de puertas. Cada una de las siguientes M líneas contiene una descripción de la puerta – los números de las habitaciones a las que conduce y a las que conduce (solo se puede atravesar la puerta en una dirección), así como un número entero que se suma a la cantidad de conocimiento al atravesar la puerta (este número no superar 10000 en módulo). Las puertas pueden llevar de una habitación a sí misma, puede haber más de una puerta entre dos habitaciones.
Salida:
Mostrar ":)" – si puede obtener una cantidad ilimitada de conocimiento, ":(" – si no se puede pasar el laberinto, y la cantidad máxima de conocimiento obtenido de otra manera.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
2 2
1 2 3
1 2 7
|
7 |