辺のラベル \(w\) が \( w\ \mathrm{OR}\ x=x\) を満たす辺のみを通って頂点 \(1\) から頂点 \(N\) まで到達できるか？という判定問題を考えます。この判定問題が Yes になる \(x\) の集合を \(X\) とすると、 \(\min X\) が問題の答えとなります。

ここで、 \(x\in X\) なら \(x\ \mathrm{OR}\ 2^k \in X\) が成立することを考えると、以下のような貪欲法が正当であることが分かります。

• \(x=2^{30}-1\) とする。この \(x\) は \(x\in X\) を満たす。
• \(k=29,28,\ldots,0\) の順に以下の操作を行う。
  • \(x\) の \(k\) ビット目を \(0\) にできるか調べる。つまり、 \(x'=x-2^k\) が \(X\) に含まれるか判定し、含まれるなら \(x\) を \(x'\) に置き換える。含まれないなら何もしない。

各判定問題は DSU などを使って解くことができます。

以上を適切に実装することでこの問題を解くことができます。計算量は \(O((N+M)\alpha(N)\log \max_i w_i)\) や \(O((N+M)\log \max_i w_i)\) です。

実装例(Python3)

from atcoder import dsu

n, m = map(int, input().split())
a = [()] * m
for i in range(m):
    u, v, w = map(int, input().split())
    a[i] = (u - 1, v - 1, w)
x = (1 << 30) - 1
for k in range(29, -1, -1):
    x ^= 1 << k
    d = dsu.DSU(n)
    for u, v, w in a:
        if (x | w) == x:
            d.merge(u, v)
    if not d.same(0, n - 1):
        x |= 1 << k
print(x)