In Summer Computer School (LKSH) built ride the Labyrinth of knowledge. "The Labyrinth is an n rooms, numbered from 1 to n, between some of which have doors. When a person goes through the door, the indicator of his knowledge is changed to a certain amount fixed for the door. The entrance to the maze is located in room 1, the output - in room n. Each student is a maze of exactly once and comes in either a training group, depending on the amount of accumulated knowledge (at the entrance to the labyrinth, the figure is zero). Your task is to show the best results.

Input

The first line contains the integers n (1 ≤ n ≤ 2000) - the number of rooms and m (1 ≤ m ≤ 10000) - number of doors. In each of the following m lines contains a description of the door - number of rooms, from which it leads and to which it leads (through the door you can walk in one direction only) and an integer that is added to the amount of knowledge as it passes through the door (this number in absolute value does not exceed 10000). Doors can carry it from room to itself, between the two rooms can be more than one door.

Output

Print ":)" if you can get infinitely large store of knowledge ":(" - if you can not go through a maze, and the maximum amount of accumulated knowledge otherwise.