問題文

頂点に 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 にたどり着いたときのたこさんウインナーの足の本数として考えられる最小値と最大値を求めてください。

制約

• 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}
• 入力で与えられるグラフは単純連結
• 入力はすべて整数

入力例 1

4 4
1 2 6
2 3 1
3 4 4
1 4 7

出力例 1

1 7

はじめ、たこさんウィンナーは足が 1 本の状態で、頂点 1 にいます。例えば、以下のように移動することができます。

• 辺 4 を選び、y = 1 とすると足の本数が 1 本の状態で、頂点 4 に移動します。

このように移動すると足の本数が 1 本の状態で頂点 4 に移動できます。また、以下のように移動することもできます。

• 辺 4 を選び、y = 7 とすると足の本数が 7 本の状態で、頂点 4 に移動します。

このように移動すると足の本数が 7 本の状態で頂点 4 に移動できます。これが、頂点 4 に着いたときの足の本数の最小値と最大値を達成する方法です。

入力例 2

4 4
1 2 100
1 3 200
2 4 1
3 4 5

出力例 2

-1 -1

入力例 3

6 10
3 5 1
1 5 2
1 3 3
3 4 4
1 6 5
4 6 6
5 6 7
2 4 8
2 5 9
1 2 10

出力例 3

1 7