Переклад боргів#11525

Переклад боргів

1 секунда

256 мегабайтів

Легка

Уявіть, що у вашій компанії є три особи: $A$ , $B$ та $C$ . При цьому $A$ винен $B$ $20$ гривень, а $B$ винен $C$ $20$ гривень. Загальна сума заборгованостей становить $40$ гривень. Можна помітити, що такі заборгованості не є оптимальними. Перерозподілимо їх так: нехай $A$ винен $C$ $20$ гривень, а $B$ нікому нічого не винен. Сенс заборгованостей не змінився, але загальна сума зменшилася до $20$ гривень.

Це завдання узагальнює наведений приклад. Уявіть, що у вашій компанії $n$ осіб, і відомі заборгованості між ними. Оптимізуйте ці заборгованості, не змінюючи їх сенсу. Тобто, для кожної особи різниця між тим, скільки вона повинна віддати, і скільки отримати, повинна залишитися незмінною. Виведіть мінімальну суму всіх заборгованостей в оптимальному розподілі. Ознайомтеся з поясненнями тестових прикладів для кращого розуміння завдання.

Вхідні дані

У першому рядку записані два цілі числа $n$ і $m (1 \leq n \leq 100; 0 \leq m \leq 1 0^{4})$ m~(1 \le n \le 100;~ 0 \le m \le 10^4). У наступних $m$ рядках задані заборгованості. У $i$ -му рядку записані три цілі числа $a_{i}, b_{i}, c_{i} (1 \leq a_{i}, b_{i} \leq n; a_{i} \neq = b_{i}; 1 \leq c_{i} \leq 100)$ a_i, b_i, c_i ~(1 \le a_i, b_i \le n;~ a_i \ne b_i;~ 1 \le c_i \le 100), які означають, що особа $a_{i}$ a_i винна особі $b_{i} c_{i}$ b_i~c_i гривень.

Вважайте, що люди пронумеровані від $1$ до $n$ цілими числами.

Гарантується, що одна і та ж пара людей зустрічається у вхідних даних не більше одного разу. У вхідних даних не зустрічається одночасно пара людей $(x, y)$ і пара людей $(y, x)$ .

Вихідні дані

Виведіть єдине ціле число — мінімальну суму заборгованостей в оптимальному розподілі.

Приклади

У першому прикладі можна вважати, що особа з номером $1$ винна особі з номером $2$ $8$ гривень, особі з номером $3$ $1$ гривню і особі з номером $4$ $1$ гривню. Більше ніхто нікому не винен. У підсумку сумарна заборгованість дорівнює $10$ .

У другому прикладі немає ніяких заборгованостей.

У третьому прикладі можна анулювати всі заборгованості.

Приклад 1

Приклад 2

Приклад 3