問題
スズメバチは＊＊＊＊を狙っている。
しかし、＊＊＊＊の家は複数あるため、追いかけてもすぐに逃げ込まれてしまう。
そこで、スズメバチは家から家を結ぶ道に100m間隔で巣を設置することにした。
巣がある道を辿れば全ての家に到達できるように設置するが、一筆書きで辿れる必要はない。
巣の設置には労力がいるので、設置する巣の数を最小限にする必要がある。
家と家を結ぶ道のデータを読み込んで、必要最小限の巣の数を出力するプログラムを作成して下さい。
ただし、家と家の間の距離は200m以上で、100の倍数で与えられます。
おのおのの家から一番近い巣までの距離は100mで、＊＊＊＊の家は100箇所以下です。家そのものには巣を設置しません。
※結ぶ家が同じでも、距離が違う道が存在することに注意してください。
入力
複数のデータセットが与えられます。各データセットは以下の形式で与えられます。
n m a1 b1 d1 a1 b2 d2 . . am bm dm
各データセットの最初の 1 行には家の箇所数 n (2 ≤ n ≤ 100) が与えられます。続いて家と家を結ぶ道の数 m (2 ≤ m ≤ 50000) が与えられます。続く m 行に 3 つの数数 ai bi di が与えられます。ai bi は家の番号です。家の番号は 0 番から n - 1 番まで振られています。ai bi はそれらを結ぶ道があることを示し、di (200 ≤ di ≤ 10000) は ai bi 間の距離を表しています。
n が 0 のとき入力の最後とします。データセットの数は 20 を超えません。
(画像ガバガバなのは許してください。)
出力
各データセットに対して、必要最小限の巣の数を１行に出力して下さい。
入出力例
入力例1
4 4 0 1 1500 0 2 2000 1 2 600 1 3 500 0
出力例1
23