Attraction "Labyrinth of Knowledge" was built at the Summer Computer School (LCS). The labyrinth consists of N rooms, numbered from 1 to N, some of which have doors between them. When a person passes through a door, the indicator of his knowledge changes by a certain amount fixed for this door. The entrance to the labyrinth is in room 1, the exit – in room N. Each student goes through the maze exactly once and gets into one or another study group depending on the amount of knowledge gained (when entering the maze, this indicator is zero). Your task is to show the best result.
Input:
The first line of the input contains integers N (1 <= N <= 2000) – number of rooms and M (1 <= M <= 10000) – Number of doors. Each of the next M lines contains a description of the door – the numbers of the rooms from which it leads and to which it leads (you can only walk through the door in one direction), as well as an integer that is added to the amount of knowledge when passing through the door (this number does not exceed 10000 in modulo). Doors can lead from a room to itself, there can be more than one door between two rooms.
Output:
Display ":)" – if you can get an unlimited amount of knowledge, ":(" – if the labyrinth cannot be passed, and the maximum amount of knowledge gained otherwise.
Examples
| # |
Input |
Output |
| 1 |
2 2
1 2 3
1 2 7
|
7 |