L. Построить потенциалы

Как классная задача L, но потенциалы надо не проверить, а построить.

Способ ровно один и он же — первый шаг алгоритма Джонсона: положить все $p_v$ равными нулю и выполнить Форда — Беллмана. Это то же самое, что добавить фиктивную вершину с рёбрами нулевого веса во все остальные и посчитать от неё расстояния.

Полученные значения удовлетворяют $p_v \le p_u + w$ для каждого ребра, а это и есть условие $w + p_u - p_v \ge 0$.

Если в графе есть отрицательный цикл, потенциалов не существует: вдоль цикла сумма пересчитанных весов равна сумме исходных, а она отрицательна, и неотрицательными все слагаемые быть не могут.

Чтобы ответ был единственным, зафиксируем: все $p_v$ изначально нули, ровно $n - 1$ фаз, рёбра в порядке ввода, при отсутствии изменений останавливаемся.

Первая строка содержит числа $n$ ($1 \le n \le 100$) и $m$ ($0 \le m \le 10^4$).

Далее идут $m$ строк с рёбрами: начало, конец и вес ($-100 \le w \le 100$).

NO, если потенциалов не существует.

Иначе YES и во второй строке $n$ значений.