AT_abc410_d [ABC410D] XOR Shortest Walk

There is a directed graph with $ N $ vertices and $ M $ edges, where vertices are numbered from $ 1 $ to $ N $ and edges are numbered from $ 1 $ to $ M $ . Edge $ i $ is a directed edge from vertex $ A_i $ to vertex $ B_i $ with **weight** $ W_i $ . Find the minimum value of the bitwise $ \mathrm{XOR} $ of the weights of edges included in a walk from vertex $ 1 $ to vertex $ N $ . What is a walk from vertex $ 1 $ to vertex $ N $ ? Intuitively, it is "a path from vertex $ 1 $ to vertex $ N $ that may visit the same vertex or edge multiple times." Formally, it is a sequence of edges $ (e_1,\ldots,e_k) $ that satisfies all of the following conditions: - $ e_1 $ starts at vertex $ 1 $ . - For all $ 1 \leq i < k $ , the endpoint of $ e_i $ and the starting point of $ e_{i+1} $ are the same. - $ e_k $ ends at vertex $ N $ . What is the bitwise $ \mathrm{XOR} $ operation? The bitwise $ \mathrm{XOR} $ of non-negative integers $ A $ and $ B $ , denoted $ A\ \mathrm{XOR}\ B $ , is defined as follows: - When $ A\ \mathrm{XOR}\ B $ is written in binary, the digit at the $ 2^k $ place ( $ k \geq 0 $ ) is $ 1 $ if exactly one of the digits at the $ 2^k $ place of $ A $ and $ B $ in binary is $ 1 $ , and $ 0 $ otherwise. For example, $ 3\ \mathrm{XOR}\ 5 = 6 $ (in binary: $ 011\ \mathrm{XOR}\ 101 = 110 $ ). In general, the bitwise $ \mathrm{XOR} $ of $ k $ non-negative integers $ p_1, p_2, p_3, \dots, p_k $ is defined as $ (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k) $ , and it can be proved that this does not depend on the order of $ p_1, p_2, p_3, \dots p_k $ .

The input is given from Standard Input in the following format: > $ N $ $ M $ $ A_1 $ $ B_1 $ $ W_1 $ $ A_2 $ $ B_2 $ $ W_2 $ $ \vdots $ $ A_M $ $ B_M $ $ W_M $

If there is no walk from vertex $ 1 $ to vertex $ N $ , output `-1`. If there is a walk from vertex $ 1 $ to vertex $ N $ , output the minimum value of the bitwise $ \mathrm{XOR} $ of the weights of edges included in such a walk.

### Sample Explanation 1 The bitwise $ \mathrm{XOR} $ of the weights of edges included in the walk (edge $ 1 $ , edge $ 2 $ ) is $ 1 $ . ### Sample Explanation 2 The bitwise $ \mathrm{XOR} $ of the weights of edges included in the walk (edge $ 1 $ , edge $ 2 $ , edge $ 3 $ , edge $ 4 $ ) is $ 0 $ . Note that the walk may include vertex $ N $ in the middle. ### Sample Explanation 3 If there is no walk from vertex $ 1 $ to vertex $ N $ , output `-1`. ### Constraints - $ 2 \leq N \leq 1000 $ - $ 0 \leq M \leq 1000 $ - $ 1 \leq A_i,B_i \leq N $ - $ 0 \leq W_i < 2^{10} $ - All input values are integers.