B. I.O.U.

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$A$, $B$, $C$ гэсэн 3 найз байсан ба $A$ $B$-д $20$ рублийн өртэй, $B$ $C$-д бас $20$ рублийн өртэй гэж үзье. Энд нийт өрийн хэмжээ $40$ рубль. Таны харж байгаагаар өрийн байдал тийм ч зөв биш байна. Үүнийг $A$ $C$-д $20$ рублийн өртэй бөгөөд $B$ хэнд ч өргүй гэж өөрчилж болно. Өрийн байдал хэвэндээ боловч нийт өрийн хэмжээ $20$ рубль болж өөрчлөгдсөн байна.

Таны даалгавар дээр байгаачлан өрийг хялбарчлах юм. Нийт $n$ найзууд байсан ба хүн бүрийн бусаддаа өгөх өрийн хэмжээ мэдэгдэж байгаа. Өрийн сүлжээг бүх хүний хувьд анх авах байсан мөнгө болон төлөх мөнгөний зөрүү хэвэндээ байхаар хялбарчил. Өрийн сүлжээг хялбарчилсны дараа байж болох хамгийн бага өрийн нийлбэрийг хэвлэ. Бодлогын тавилыг илүү сайн ойлгохыг хүсвэл жишээ тестийг хараарай.

Оролт

Эхний мөрөнд хүмүүсийн тоо $n$ болон одоо байгаа өрийн тоо $m$ ($1 ≤ n ≤ 100$; $0 ≤ m ≤ 10^4$) өгөгдөнө. Дараагийн $m$ мөрөнд өрүүдийн мэдээлэл байх бөгөөд $i$-р мөр $a_i$ хүний $b_i$ хүнд төлөх өрийн хэмжээ болох $c_i$ ($1 ≤ a_i, b_i ≤ n$; $a_i ≠ bi$; $1 ≤ c_i ≤ 100$)-г агуулна.

Хүмүүсийг $1$-с $n$ хүртэл дугаарлагдсан гэж үзээрэй.

Оролтонд нэг хос хамгийн ихдээ $1$ л удаа тааралдана. Жишээ нь ($x, y$) ба ($y, x$) хосыг агуулахгүй

Гаралт

Зөв хялбарчилгааны дараах өрийн нийлбэр болох ганц тоог хэвлэ.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
5 3
1 2 10
2 3 1
2 4 1
Гаралт
10
Оролт
3 0
Гаралт
0
Оролт
4 3
1 2 1
2 3 1
3 1 1
Гаралт
0

Тэмдэглэл

In the first sample, you can assume that person number 1 owes 8 rubles to person number 2, 1 ruble to person number 3 and 1 ruble to person number 4. He doesn't owe anybody else anything. In the end, the total debt equals 10.

In the second sample, there are no debts.

In the third sample, you can annul all the debts.

Сэтгэгдлүүдийг ачааллаж байна...