Consider the following decision problem: is vertex \(N\) reachable from vertex \(1\) only via edges with labels \(w\) such that \( w\ \mathrm{OR}\ x=x\)? For the set of \(X\) of such integers \(x\), the answer is \(\min X\).

Here, if \(x\in X\), then \(x\ \mathrm{OR}\ 2^k \in X\), so the following greedy algorithm is valid:

• Let \(x=2^{30}-1\). This \(x\) satisfies \(x\in X\).
• For \(k=29,28,\ldots,0\), do the following:
  • Determine if the \(k\)-th bit of \(x\) can be made \(0\). That is, check if \(x'=x-2^k\) is in \(X\). If it is, replace \(x\) with \(x'\), and do nothing otherwise.

Each decision problem can be solved with, for example, DSU (Disjoint Set Union).

The problem can be solved by appropriately implementing the algorithm. The time complexity is \(O((N+M)\alpha(N)\log \max_i w_i)\) or \(O((N+M)\log \max_i w_i)\).

Sample code (Python 3)

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)