Labyrinth of knowledge#1454
At the International Summer Informatics Camp (ISIC), an attraction called the "Labyrinth of knowledge" was created. The Labyrinth consists of rooms, numbered from to , with doors connecting some pairs of rooms. When a person passes through a door, their knowledge indicator is changed by a fixed integer associated with that door. The entrance to the labyrinth is in room , and the exit is in room . Each student passes through the labyrinth exactly once, starting with a knowledge value of zero. Your task is to determine the best possible result.
The first line contains two integers (1 \le n \le 2000) — the number of rooms, and (1 \le m \le 10000) — the number of doors. The following lines each describe a door: the number of the room it starts from, the number of the room it leads to (doors are one way only), and an integer that is added to the knowledge when passing through the door (the absolute value does not exceed ). A door may lead from a room to itself, and there may be multiple doors between two rooms.
Print ":)" if it is possible to obtain an unlimited amount of knowledge, ":(" if it is impossible to pass through the labyrinth, and otherwise print the maximum possible amount of knowledge that can be accumulated.
Example 1