D. Уменьшаем долги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим компанию из $$$n$$$ людей, пронумерованных от $$$1$$$ до $$$n$$$. Они используют бурли, чтобы платить за товары и услуги. Иногда человеку не хватает денег на какую-либо покупку, тогда он занимает деньги у другого человека с намерением потом отдать их с процентами. Мы обозначим за $$$d(a,b)$$$ сумму, которую $$$a$$$ должен отдать $$$b$$$, или $$$0$$$, если долга нет.

Иногда система долгов может усложняться — например, в ситуации, когда один человек дал на время денег другому, но первому самому не хватает денег на покупку, а второй еще не отдал долг. Тогда первому человеку придется занимать у кого-то ещё.

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

  1. Пусть $$$d(a,b) > 0$$$ и $$$d(c,d) > 0$$$, при этом $$$a \neq c$$$ или $$$b \neq d$$$. Можно уменьшить $$$d(a,b)$$$ и $$$d(c,d)$$$ на $$$z$$$ и при этом увеличить $$$d(c,b)$$$ и $$$d(a,d)$$$ на $$$z$$$, если $$$0 < z \leq \min(d(a,b),d(c,d))$$$.
  2. Пусть $$$d(a,a) > 0$$$. Можно уменьшить $$$d(a,a)$$$ до $$$0$$$.

Суммарный долг определяется следующей величиной:

$$$$$$\Sigma_d = \sum_{a,b} d(a,b)$$$$$$

Вы можете использовать ранее описанные операции в любом порядке. Ваша цель — минимизировать суммарный долг. Обратите внимание, что не обязательно минимизировать количество ненулевых долгов, только суммарный долг должен стать как можно меньше.

Входные данные

В первой строке заданы два целых числа $$$n$$$ ($$$1 \leq n \leq 10^5$$$) и $$$m$$$ ($$$0 \leq m \leq 3\cdot 10^5$$$) — количество людей и долгов, соответственно.

Далее следуют $$$m$$$ строк, каждая из которых содержит три целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$), $$$d_i$$$ ($$$1 \leq d_i \leq 10^9$$$), обозначающих, что человек $$$u_i$$$ должен $$$d_i$$$ бурлей человеку $$$v_i$$$.

Выходные данные

В первой строке выведите число $$$m'$$$ ($$$0 \leq m' \leq 3\cdot 10^5$$$) — количество долгов после уменьшения системы долгов. Можно показать, что всегда существует способ упростить систему до минимального суммарного долга с соблюдением этого условия.

Далее выведите $$$m'$$$ строк, $$$i$$$-я из которых содержит три целых числа $$$u_i, v_i, d_i$$$, обозначающих, что человек $$$u_i$$$ должен отдать человеку $$$v_i$$$ ровно $$$d_i$$$ бурлей. На эти числа накладываются следующие ограничения: $$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$ и $$$0 < d_i \leq 10^{18}$$$.

Для каждой пары $$$i \neq j$$$ должно соблюдаться условие $$$u_i \neq u_j$$$ или условие $$$v_i \neq v_j$$$. Иными словами, каждая пара людей должна встречаться в выходных данных только один раз.

Примеры
Входные данные
3 2
1 2 10
2 3 5
Выходные данные
2
1 2 5
1 3 5
Входные данные
3 3
1 2 10
2 3 15
3 1 10
Выходные данные
1
2 3 5
Входные данные
4 2
1 2 12
3 4 8
Выходные данные
2
1 2 12
3 4 8
Входные данные
3 4
2 3 1
2 3 2
2 3 4
2 3 8
Выходные данные
1
2 3 15
Примечание

В первом примере одна из оптимальных последовательностей операций — следующая:

  1. Проведём операцию первого типа с $$$a = 1$$$, $$$b = 2$$$, $$$c = 2$$$, $$$d = 3$$$ и $$$z = 5$$$. В результате система долгов становится следующей: $$$d(1, 2) = 5$$$, $$$d(2, 2) = 5$$$, $$$d(1, 3) = 5$$$, все остальные долги равны $$$0$$$;
  2. Проведём операцию второго типа с $$$a = 2$$$. В результате система долгов становится следующей: $$$d(1, 2) = 5$$$, $$$d(1, 3) = 5$$$, все остальные долги равны $$$0$$$.

Во втором примере одна из оптимальных последовательностей операций — следующая:

  1. Проведём операцию первого типа с $$$a = 1$$$, $$$b = 2$$$, $$$c = 3$$$, $$$d = 1$$$ и $$$z = 10$$$. В результате система долгов становится следующей: $$$d(3, 2) = 10$$$, $$$d(2, 3) = 15$$$, $$$d(1, 1) = 10$$$, все остальные долги равны $$$0$$$;
  2. проведём операцию первого типа с $$$a = 2$$$, $$$b = 3$$$, $$$c = 3$$$, $$$d = 2$$$ и $$$z = 10$$$. В результате система долгов становится следующей: $$$d(2, 2) = 10$$$, $$$d(3, 3) = 10$$$, $$$d(2, 3) = 5$$$, $$$d(1, 1) = 10$$$, все остальные долги равны $$$0$$$;
  3. Проведём операцию второго типа с $$$a = 2$$$. В результате система долгов становится следующей: $$$d(3, 3) = 10$$$, $$$d(2, 3) = 5$$$, $$$d(1, 1) = 10$$$, все остальные долги равны $$$0$$$;
  4. Проведём операцию второго типа с $$$a = 3$$$. В результате система долгов становится следующей: $$$d(2, 3) = 5$$$, $$$d(1, 1) = 10$$$, все остальные долги равны $$$0$$$;
  5. Проведём операцию второго типа с $$$a = 1$$$. В результате система долгов становится следующей: $$$d(2, 3) = 5$$$, все остальные долги равны $$$0$$$.