G. Нефть

Однажды в городе П. решили построить нефтяную сеть. Для этого было построено n транспортных узлов, которые соединялись между собой m нефтепроводами. Стоит помнить, что нефть по трубопроводу течет только в одну сторону. Из-за приближающегося срока сдачи проекта в эксплуатацию подрядная организация начала очень быстро сооружать узлы и трубопроводы. Для каждого нефтепровода известно направление движения и объем протекающей нефти, измеренный в литрах в секунду. Не трудно заметить, что при этом в некоторых узлах может возникнуть избыток/недостаток нефти в том смысле, что втекает/вытекает нефти больше, чем вытекает/втекает. Требуется определить в каких вершинах необходимо докачивать нефть, а в каких сливать неиспользуемый избыток для того, чтобы соблюдался баланс (количество втекающей нефти должно быть равно количеству вытекающей с учето дополнительной откачки/долива).

Формат входного файла

В первой строке содержатся целые числа n и m (1 ≤ n, m ≤ 100000). В следующих m строках находятся описания нефтепроводов: тройка чисел u, v, c, где u – номер узла, из которого вытекает нефть в узел v со скоростью c литров в секунду (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ c ≤ 10000). Узлы нефтесети пронумерованы целыми числами от 1 до n, между двумя узлами может быть более одного нефтепровода.

Формат выходного файла

В выходной файл выведите n чисел – информацию об изменениях в каждом узле: i-ое число равно c_i и удовлетворяет одному из следующих условий:

1. если c_i отрицательное, то из узла i необходимо дополнительно слить -c_i (л/сек),
2. если c_i положительное, то в узел i необходимо дополнительно закачать c_i (л/сек),
3. если c_i равно нулю, то производить изменения с узлом i не нужно, так как соблюдается баланс объема втекающей и вытекающей нефти.

Пример: