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.

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

struct DSU
{
    vector<int> fa;
    DSU(int n) : fa(n+1)
    {
        iota(fa.begin(),fa.end(),0);
    }
    int find(int x)
    {
        while(x != fa[x]) x = fa[x] = fa[fa[x]];
        return x;
    }
    bool same(int x,int y)
    {
        return find(x) == find(y);
    }
    bool merge(int x,int y)
    {
        x = find(x);
        y = find(y);
        if(x==y) return false;
        if(x > y) swap(x,y);
        fa[y] = x;
        return true;
    }
};
void solve()
{   
    int n,m;
    cin >> n >> m;
    vector<tuple<int,int,int>> edge;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        edge.push_back({u,v,w});
    }
    auto check = [&](vector<tuple<int,int,int>>& edge,int ban)
    {
        DSU dsu(n);
        for(auto& [u,v,w] : edge)
        {
            if(w & ban) continue; // 如果该边权比特位中包含被禁止的比特位，则跳过
            else dsu.merge(u,v);
        }
        return dsu.same(1,n);
    };
    int ans = 0;
    int bit = 0;
    for(int i=30;i>=0;i--)
    {
        int ban = bit | (1LL << i); //尽量使此位不为1，检测此时是否可以保证联通
        if(check(edge,ban)) bit = ban;
        // 若可以联通，为使答案最小则这个1一定可以不要，将此1加入禁止比特位
        else ans |= (1LL << i); // 否则答案必须有这个1
    }
    cout << ans << endl;
}