AT_KeioPC2025_h Takosan Takusan

頂点に $ 1 $ から $ N $ の、辺に $ 1 $ から $ M $ の番号がついた $ N $ 頂点 $ M $ 辺の単純連結無向グラフが与えられます。辺 $ i $ は頂点 $ u_i $ と頂点 $ v_i $ を結んでおり、整数 $ A_i $ が書かれています。 いま、頂点 $ 1 $ にたこさんウインナーがいます。たこさんウインナーは足を $ 1 $ 本持っています。たこさんウインナーは以下の行動を繰り返すことで頂点 $ N $ へ向かおうと考えています。 1. 現在の頂点に接続する辺を $ 1 $ つ選ぶ。選んだ辺を辺 $ i $ とする。 2. たこさんウインナーの現在の足の本数を $ x $ 本として、 $ x \le y $ かつ $ y\ \mathrm{OR}\ A_i = A_i $ を満たすような整数 $ y $ を選ぶ。そして、足の本数を $ y $ 本に増やし辺 $ i $ を渡る。 ここで $ a\ \mathrm{OR}\ b $ は $ a $ と $ b $ のビットごとの論理和を表します。 たこさんウインナーが頂点 $ N $ に到達することが可能か判定し、可能な場合、初めて頂点 $ N $ にたどり着いたときのたこさんウインナーの足の本数として考えられる最小値と最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N\ M $ $ u_1\ v_1\ A_1 $ $ u_2\ v_2\ A_2 $ $ \vdots $ $ u_M\ v_M\ A_M $

たこさんウインナーが初めて頂点 $ N $ にたどり着いたときのたこさんウインナーの足の本数として考えられる最小値と最大値をこの順でスペース区切りで $ 1 $ 行に出力せよ。 どのように行動しても頂点 $ N $ にたどり着くことができない場合は `-1 -1` を出力せよ。

### Sample Explanation 1 はじめ、たこさんウィンナーは足が $ 1 $ 本の状態で、頂点 $ 1 $ にいます。例えば、以下のように移動することができます。 - 辺 $ 4 $ を選び、 $ y = 1 $ とすると足の本数が $ 1 $ 本の状態で、頂点 $ 4 $ に移動します。 このように移動すると足の本数が $ 1 $ 本の状態で頂点 $ 4 $ に移動できます。また、以下のように移動することもできます。 - 辺 $ 4 $ を選び、 $ y = 7 $ とすると足の本数が $ 7 $ 本の状態で、頂点 $ 4 $ に移動します。 このように移動すると足の本数が $ 7 $ 本の状態で頂点 $ 4 $ に移動できます。これが、頂点 $ 4 $ に着いたときの足の本数の最小値と最大値を達成する方法です。 ### Constraints - $ 2 \le N \le 2 \times 10^5 $ - $ 1 \le M \le 2 \times 10^5 $ - $ 1 \le u_i, v_i \le N $ - $ 0 \le A_i \lt 2^{30} $ - 入力で与えられるグラフは単純連結 - 入力はすべて整数