Оптимальний потік величини 1#4582
Дано орієнтований граф з вершинами і ребрами, де вершина — це джерело, а вершина — стік, при цьому кожне ребро має свою вартість.
Ваше завдання — визначити оптимальний потік величини через цю мережу, тобто потік величини , що має мінімальну вартість. Хоча вартості ребер можуть бути від’ємними, у графі гарантується відсутність циклів із від’ємною вагою. Хоча місткості явно не задано, відомо, що вони не менше .
Перший рядок містить два цілі числа та (2 \leq n \leq 1000, 0 \leq m \leq 10000). Наступні рядків містять по три цілі числа , та — ребро з вершини у вершину з вартістю (1 \leq x, y \leq n, -1000 \leq p \leq 1000). У графі можуть бути петлі та кратні ребра.
Виведіть одне ціле число — вартість оптимального потоку величини . Якщо провести потік величини у мережі неможливо, виведіть NO.
Приклад 1