Оптимальний потік величини 1

Задано орієнтовний граф з n вершин і m ребер. Вершина 1 є витоком, вершина n — стоком. Кожному ребру приписано деяку ціну.

Знайдіть у заданій мережі оптимальний потік величини 1, тобто потік величини 1, який має найменшу вартість. Ціни ребер можуть бути відємними, проте відомо, що граф не містить циклів від'ємної ваги. Пропускні здатності вам не задані, про них відомо, що вони не менші 1.

Вхідні дані

У першому рядку задані числа n і m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 10000). Далі йде m рядків з трійками цілих чисел x, y, p - ребро з x в y має ціну p (1 ≤ x, y ≤ n, -1000 ≤ p ≤ 1000). У графі можуть бути петлі та кратні ребра.

Вихідні дані

Виведіть одне ціле число - вартість оптимального потоку величини 1. У випадку якщо у мережі не існує потоку величини 1, виведіть NO.

Приклади