У школі збудували атракціон "Лабіринт знань". Лабіринт є \(N\) кімнат, занумерованих від 1 до \(N\), між деякими з яких є двері. Коли людина проходить через двері, показник його знань змінюється на певну величину, фіксовану для цих дверей. Вхід до лабіринту знаходиться в кімнаті 1, вихід – у кімнаті \(N\). Кожен учень проходить лабіринт рівно один раз і потрапляє в ту чи іншу навчальну групу в залежності від кількості набраних знань (при вході в лабіринт цей показник дорівнює нулю). Ваше завдання показати найкращий результат.

Формат вхідних даних

Перший рядок вхідних даних містить цілі числа \(N\) \((1 \le N \le 2000)\) – кількість кімнат та \(M\) \((1 \le M \le 10000)\) – кількість дверей.

У кожному з наступних \(M\) рядків міститься опис дверей - номери кімнат, з яких вона веде і в яку вона веде (через двері можна ходити тільки в одному напрямку), а також ціле число, яке додається до знань при проходженні через двері (це число за модулем не перевищує 10000). Двері можуть вести з кімнати в неї саму, між двома кімнатами може бути більше однієї двері.

Формат вихідних даних

Виведіть ":)" – якщо можна отримати необмежено великий запас знань, ":(" – якщо лабіринт пройти не можна, і максимальна кількість набраних знань інакше).

Приклад вхідних даних

2 2
1 2 3
1 2 7

Приклад вихідних даних

7