オランダ旅行

/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