AT_abc408_e [ABC408E] Minimum OR Path

頂点に $ 1 $ から $ N $ の、辺に $ 1 $ から $ M $ の番号がついた $ N $ 頂点 $ M $ 辺の自己ループを持たない連結な無向グラフが与えられます。辺 $ i $ は頂点 $ u_i $ と頂点 $ v_i $ を双方向に結んでおり、ラベル $ w_i $ がつけられています。 頂点 $ 1 $ から頂点 $ N $ までの単純パス（同じ頂点を $ 2 $ 度以上通らないパス）のうち、パスに含まれる辺につけられたラベルの総ビット単位 $ \mathrm{OR} $ としてあり得る最小値を求めてください。 ビット単位 $ \mathrm{OR} $ 演算とは 非負整数 $ A, B $ のビット単位 $ \mathrm{OR} $ 、 $ A\ \mathrm{OR}\ B $ は以下のように定義されます。 - $ A\ \mathrm{OR}\ B $ を二進表記した際の $ 2^k $ ( $ k \geq 0 $ ) の位の数は、 $ A, B $ を二進表記した際の $ 2^k $ の位の数のうち少なくとも片方が $ 1 $ であれば $ 1 $ 、そうでなければ $ 0 $ である。 例えば、 $ 3\ \mathrm{OR}\ 5 = 7 $ となります (二進表記すると: $ 011\ \mathrm{OR}\ 101 = 111 $ )。 一般に $ k $ 個の非負整数 $ p_1, p_2, p_3, \dots, p_k $ のビット単位 $ \mathrm{OR} $ は $ (\dots ((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\ \dots\ \mathrm{OR}\ p_k) $ と定義され、これは $ p_1, p_2, p_3, \dots p_k $ の順番によらないことが証明できます。

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

答えを出力せよ。

### Sample Explanation 1 辺 $ 1,3,5 $ を順番に通り頂点 $ 1,2,3,4 $ を順番に通ると総ビット単位 $ \mathrm{OR} $ は $ 1\ \mathrm{OR}\ 2\ \mathrm{OR}\ 3=3 $ となります。 総ビット単位 $ \mathrm{OR} $ を $ 3 $ より小さくすることはできないので、 $ 3 $ を出力してください。 ### Sample Explanation 2 グラフには多重辺が存在する場合もあります。 ### Constraints - $ 2\le N\le 2\times 10^5 $ - $ N-1\le M\le 2\times 10^5 $ - $ 1\le u_i < v_i\le N $ - $ 0\le w_i< 2^{30} $ - 与えられるグラフは連結である - 入力される値は全て整数