Problem
アトラクション「Labyrinth of Knowledge」は、サマー コンピューター スクール (LCS) に建設されました。迷宮は、1 から N までの番号が付けられた N 個の部屋で構成されており、それらの間にドアがあるものもあります。人がドアを通過すると、その人の知識の指標は、このドアに固定された一定量だけ変化します。迷宮への入り口は部屋 1 にあり、出口 –各生徒は迷路を正確に 1 回通過し、得られた知識の量に応じて、1 つまたは別の研究グループに入ります (迷路に入るとき、この指標はゼロです)。あなたの仕事は最高の結果を示すことです。
入力:
入力の最初の行には、整数 N (1 <= N <= 2000) が含まれます –部屋数と M (1 <= M <= 10000) –ドアの数。次の各 M 行には、ドアの説明が含まれています –ドアを通過するときに知識量に追加される整数 (この番号はモジュロで 10000 を超える)。ドアは部屋からそれ自体につながることができ、2 つの部屋の間に複数のドアがある場合があります。
出力:
表示 ":)" –無制限の量の知識を取得できる場合、「:(」 – 迷宮を通過できない場合、それ以外の場合は最大量の知識を取得できます。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
2 2
1 2 3
1 2 7
|
7 |