E - Minimum OR Path Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

頂点に 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 の順番によらないことが証明できます。

制約

  • 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}
  • 与えられるグラフは連結である
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_M v_M w_M

出力

答えを出力せよ。

入力例 1

4 5
1 2 1
1 3 4
2 3 2
2 4 4
3 4 3

出力例 1

3

辺 1,3,5 を順番に通り頂点 1,2,3,4 を順番に通ると総ビット単位 \mathrm{OR} は 1\ \mathrm{OR}\ 2\ \mathrm{OR}\ 3=3 となります。

総ビット単位 \mathrm{OR} を 3 より小さくすることはできないので、 3 を出力してください。

入力例 2

3 5
1 2 1
1 2 2
1 2 3
1 2 4
2 3 4

出力例 2

4

グラフには多重辺が存在する場合もあります。

入力例 3

8 12
4 5 16691344
5 7 129642441
2 7 789275447
3 8 335307651
3 5 530163333
5 6 811293773
3 8 333712701
1 2 2909941
2 3 160265478
5 7 465414272
1 3 903373004
6 7 408299562

出力例 3

468549631

Score : 450 points

Problem Statement

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.

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.

Input

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

Output the answer.

Sample Input 1

4 5
1 2 1
1 3 4
2 3 2
2 4 4
3 4 3

Sample Output 1

3

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 Input 2

3 5
1 2 1
1 2 2
1 2 3
1 2 4
2 3 4

Sample Output 2

4

The graph may contain multi-edges.

Sample Input 3

8 12
4 5 16691344
5 7 129642441
2 7 789275447
3 8 335307651
3 5 530163333
5 6 811293773
3 8 333712701
1 2 2909941
2 3 160265478
5 7 465414272
1 3 903373004
6 7 408299562

Sample Output 3

468549631