AT_abc396_d [ABC396D] Minimum XOR Path

頂点に $ 1 $ から $ N $ の、辺に $ 1 $ から $ M $ の番号がついた $ N $ 頂点 $ M $ 辺の単純連結無向グラフが与えられます。辺 $ i $ は頂点 $ u_i $ と頂点 $ v_i $ を結んでおり、ラベル $ w_i $ が付けられています。 頂点 $ 1 $ から頂点 $ N $ への単純パス（同じ頂点を $ 2 $ 度以上通らないパス）のうち、パスに含まれる辺につけられたラベルの総 XOR としてあり得る最小値を求めてください。 XOR とは 非負整数 $ A,B $ の XOR $ A \oplus B $ は、以下のように定義されます。 - $ A \oplus B $ を二進表記した際の $ 2^k \, (k \geq 0) $ の位の数は、 $ A,B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $ 、そうでなければ $ 0 $ である。 例えば、 $ 3 \oplus 5 = 6 $ となります (二進表記すると: $ 011 \oplus 101=110 $ )。 一般に $ k $ 個の整数 $ p_1, \dots, p_k $ の XOR は $ (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k) $ と定義され、これは $ p_1, \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 $ から頂点 $ 4 $ への単純パスは以下の $ 2 $ つ存在します。 - 頂点 $ 1 $ $ \to $ 頂点 $ 2 $ $ \to $ 頂点 $ 4 $ - 頂点 $ 1 $ $ \to $ 頂点 $ 3 $ $ \to $ 頂点 $ 4 $ $ 1 $ つ目のパスに含まれる辺につけられたラベルの総 XOR は $ 6 $ 、 $ 2 $ つ目のパスに含まれる辺につけられたラベルの総 XOR は $ 3 $ であるため、答えは $ 3 $ です。 ### Constraints - $ 2\leq N\leq 10 $ - $ N-1\leq M\leq \frac{N(N-1)}{2} $ - $ 1\leq u_i\lt v_i\leq N $ - $ 0\leq w_i\lt 2^{60} $ - 入力で与えられるグラフは単純連結無向グラフ - 入力は全て整数