L. Проверка потенциалов

Потенциалы — способ избавиться от отрицательных весов. Если каждой вершине приписать число $p_v$ и заменить вес ребра $(u, v, w)$ на

то вес любого пути из $a$ в $b$ изменится ровно на $p_a - p_b$ — одинаково для всех путей. Значит, кратчайшие пути останутся кратчайшими. А если все новые веса окажутся неотрицательными, по такому графу можно пускать Дейкстру.

На этом стоит алгоритм Джонсона: посчитать потенциалы Фордом — Беллманом из фиктивной вершины, пересчитать веса и дальше запускать Дейкстру сколько угодно раз.

Здесь задача проще: потенциалы уже даны, надо лишь проверить, что все новые веса неотрицательны.

Проверка занимает один проход по рёбрам. Обратите внимание на переполнение: $w$ и потенциалы по модулю до $10^9$, так что $w + p_u - p_v$ может выйти за пределы 32-битного типа.

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

Вторая строка — $n$ чисел $p_v$ ($|p_v| \le 10^9$).

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

Одно слово: YES, если все пересчитанные веса неотрицательны, и NO иначе.