Hide

Problem G
オランダ旅行

/problems/goingdutch/file/statement/ja/img-0001.jpg

Picture by ben_osteen on Flickr.

あなたは友人と休暇を取ってオランダの美しい山で過ごした。休暇の間、支払の度に集金するのは面倒なので、レシートをすべて取っておいて最後に精算を行おうとした。そして、今が精算の時間だ。それぞれのレシートには誰が支払ったかを書いておいたので、その人に返金すればよい。だけど、それだと支払の回数が多すぎるので、もっと簡単に精算を行おうと考えている。誰が誰に支払おうが、最終的に全員の収支が0になればよい。そうするための支払の回数を最小にするには、どうすればよいか。全員十分な小銭を持っており、おつりが支払えなくなることはないと仮定する。

入力

先頭行は $2$ つの整数で、人数 $M$ は $1\leq M \leq 20$、レシートの枚数 $N$ は $0\leq N\leq 1000$。
その後 $N$ 行は3つの整数 $a, b, p$ で、 $0 \leq a,b < M$、 $1 \leq p \leq 1000$。$p$ さんが $p$ ユーロを $b$ さんの代わりに支払ったことを示す。

出力

単一の整数を出力する。これは、すべての精算を行うための最小の支払回数を表す。

サンプル入力 1	サンプル出力 1
4 2 0 1 1 2 3 1	2

サンプル入力 2	サンプル出力 2
5 5 0 1 3 1 2 3 2 3 3 3 4 3 4 0 3	0

サンプル入力 3	サンプル出力 3
5 4 0 1 1 0 2 1 0 3 1 0 4 1	4

Problem Gオランダ旅行

入力

出力

Problem G
オランダ旅行