Рассмотрим компанию из \(n\) людей, пронумерованных от \(1\) до \(n\). Они используют бурли, чтобы платить за товары и услуги. Иногда человеку не хватает денег на какую-либо покупку, тогда он занимает деньги у другого человека с намерением потом отдать их с процентами. Мы обозначим за \(d(a,b)\) сумму, которую \(a\) должен отдать \(b\), или \(0\), если долга нет.
Иногда система долгов может усложняться — например, в ситуации, когда один человек дал на время денег другому, но первому самому не хватает денег на покупку, а второй еще не отдал долг. Тогда первому человеку придется занимать у кого-то ещё.
Если процесс одалживания денег длится достаточно долго, система долгов может стать очень сложной и потребовать упрощения. Упрощать систему можно при помощи двух операций:
- Пусть \(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))\).
- Пусть \(d(a,a) > 0\). Можно уменьшить \(d(a,a)\) до \(0\).
Суммарный долг определяется следующей величиной:
\(\)\Sigma_d = \sum_{a,b} d(a,b)\(\)
Вы можете использовать ранее описанные операции в любом порядке. Ваша цель — минимизировать суммарный долг. Обратите внимание, что не обязательно минимизировать количество ненулевых долгов, только суммарный долг должен стать как можно меньше.
Выходные данные
В первой строке выведите число \(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\). Иными словами, каждая пара людей должна встречаться в выходных данных только один раз.
Примечание
В первом примере одна из оптимальных последовательностей операций — следующая:
- Проведём операцию первого типа с \(a = 1\), \(b = 2\), \(c = 2\), \(d = 3\) и \(z = 5\). В результате система долгов становится следующей: \(d(1, 2) = 5\), \(d(2, 2) = 5\), \(d(1, 3) = 5\), все остальные долги равны \(0\);
- Проведём операцию второго типа с \(a = 2\). В результате система долгов становится следующей: \(d(1, 2) = 5\), \(d(1, 3) = 5\), все остальные долги равны \(0\).
Во втором примере одна из оптимальных последовательностей операций — следующая:
- Проведём операцию первого типа с \(a = 1\), \(b = 2\), \(c = 3\), \(d = 1\) и \(z = 10\). В результате система долгов становится следующей: \(d(3, 2) = 10\), \(d(2, 3) = 15\), \(d(1, 1) = 10\), все остальные долги равны \(0\);
- проведём операцию первого типа с \(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\);
- Проведём операцию второго типа с \(a = 2\). В результате система долгов становится следующей: \(d(3, 3) = 10\), \(d(2, 3) = 5\), \(d(1, 1) = 10\), все остальные долги равны \(0\);
- Проведём операцию второго типа с \(a = 3\). В результате система долгов становится следующей: \(d(2, 3) = 5\), \(d(1, 1) = 10\), все остальные долги равны \(0\);
- Проведём операцию второго типа с \(a = 1\). В результате система долгов становится следующей: \(d(2, 3) = 5\), все остальные долги равны \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 2 10
2 3 5
|
2
1 2 5
1 3 5
|
|
2
|
3 3
1 2 10
2 3 15
3 1 10
|
1
2 3 5
|
|
3
|
4 2
1 2 12
3 4 8
|
2
1 2 12
3 4 8
|
|
4
|
3 4
2 3 1
2 3 2
2 3 4
2 3 8
|
1
2 3 15
|