AT_abc408_e [ABC408E] Minimum OR Path

You are given a connected undirected graph with $ N $ vertices and $ M $ edges without self-loops, where vertices are numbered from $ 1 $ to $ N $ and edges are numbered from $ 1 $ to $ M $ . Edge $ i $ connects vertices $ u_i $ and $ v_i $ bidirectionally and has a label $ w_i $ . Among the simple paths (paths that do not visit the same vertex more than once) from vertex $ 1 $ to vertex $ N $ , find the minimum possible value of the bitwise $ \mathrm{OR} $ of all labels on edges included in the path. What is bitwise $ \mathrm{OR} $ operation? The bitwise $ \mathrm{OR} $ of non-negative integers $ A $ and $ B $ , $ A\ \mathrm{OR}\ B $ , is defined as follows: - The digit in the $ 2^k $ ( $ k \geq 0 $ ) place of $ A\ \mathrm{OR}\ B $ in binary representation is $ 1 $ if at least one of the digits in the $ 2^k $ place of $ A $ and $ B $ in binary representation is $ 1 $ , and $ 0 $ otherwise. For example, $ 3\ \mathrm{OR}\ 5 = 7 $ (in binary: $ 011\ \mathrm{OR}\ 101 = 111 $ ). In general, the bitwise $ \mathrm{OR} $ of $ k $ non-negative integers $ p_1, p_2, p_3, \dots, p_k $ is defined as $ (\dots ((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\ \dots\ \mathrm{OR}\ p_k) $ , and it can be proven 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 $ $ u_1 $ $ v_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ w_2 $ $ \vdots $ $ u_M $ $ v_M $ $ w_M $

Output the answer.

### Sample Explanation 1 By traversing edges $ 1,3,5 $ in order and visiting vertices $ 1,2,3,4 $ in order, the total bitwise $ \mathrm{OR} $ is $ 1\ \mathrm{OR}\ 2\ \mathrm{OR}\ 3=3 $ . It is impossible to make the total bitwise $ \mathrm{OR} $ smaller than $ 3 $ , so output $ 3 $ . ### Sample Explanation 2 The graph may contain multi-edges. ### 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} $ - The given graph is connected. - All input values are integers.