0526 - マサヤ神

こものモニュメント

南の孤島コモノ諸島では、島民の崇める唯一神「マサヤ」の生誕100周年を記念して、大規模なイベントが催されようとしていた。
イベントの内容は様々だが、それに伴い唯一神マサヤにゆかりのある観光地に人が殺到することが予測できる。
しかし、コモノ諸島の土地は複雑に入り組んでおり、地図を持たずに踏み込んだものは帰ってこないという噂がたつほどである。
マサヤ生誕祭実行委員会はこれを受け、観光客の失踪を防ぐために、各観光地までの道に唯一神マサヤの姿を模したモニュメントを配置することを決定した。
こうすることで、モニュメントを追っていけば、唯一神マサヤにゆかりのある観光地に全て訪れることができる。

これで観光客も安全・・・かと思われたが、モニュメントを一つずつ精巧に作りすぎてしまったため制作費が伸し、当初の予定していたモニュメントの数では、マサヤ生誕祭実行委員会の予算は破産寸前となってしまった。
そこで急遽、「モニュメントは100メートル間隔で配置し、できるだけ少ない数で済ます。」という方向で計画を変更した。
マサヤ生誕祭実行委員はモニュメントの制作でクタクタである。彼らの代わりに、必要最低限のモニュメントを調べるプログラムを作ってほしい。

入力

n
m
a1 , b1 , d1
a2 , b2 , d2
:
am , bm , dm

各データセットの最初の 1 行には観光地の箇所数 n が与えられる。
続いて観光地と観光地を結ぶ通りの数 m が与えられる。
続く m 行に カンマで区切られた 3 つの数数 a_i, b_i, d_i が与えられる。
a_i, b_i は観光地の番号である。観光地の番号は 0 番から n - 1 番まで振られている。
a_i b_i はそれらを結ぶ通りがあることを示し、d_i は a_i b_i 間の道路の距離を表す。
n が 0 のとき入力の最後とする。データセットの数は 20 を超えない。

出力

各データセットに対して、必要最小限のモニュメントの数を一行に出力せよ。

制約

全ての入出力ケースについて以下を満たす。

• 観光地と観光地の間隔は200メートル以上である。
• 観光地と観光地の間隔は100の倍数で与えられる。
• 観光地から一番近いモニュメントまでの距離は100メートルである。
• 観光地の数は100箇所以内である。
• 観光地自体にはモニュメントを置く必要はない。
• 全ての観光地を一筆書きでたどれる必要はない。

入出力例

入力例1

4
4
0,1,1500
0,2,2000
1,2,600
1,3,500
0

出力例1

23

連絡

唯一神マサヤのモニュメントがほしい方はei1417までご連絡ください。