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

Вхідні дані

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

Вихідні дані

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