First, construct the following graph from the integer sequences \(X\), \(Y\), and \(Z\):

• an undirected graph with \(N\) vertices and \(M\) edges, where there is an edge between vertex \(X_i\) and vertex \(Y_i\) labeled \(Z_i\).

We will consider the solution on this graph.

First, we may consider each connected component independently. Now we assume that the graph is connected.

Fix the value \(A_1\) to be \(x\). For any edge, once the value for the vertex on one end is set, the other is uniquely determined. Thus, picking \(A_1\) determines all the value of \(A\). If any inconsistency occurs at this point, the answer is \(-1\).

Now, notice that the condition is independent for each place in \(A\)’s binary representations.

For all \(k\), the \(k\)-th bit of \(A_1\) is \(0\) or \(1\), and fixing to one of them determines the \(k\)-th bit of the others. Since we want to minimize the sum of the elements, we may try both \(0\) and \(1\) and pick whichever that makes fewer standing \(k\)-th bit. (If the number of standing bits is the same, picking anything is fine.)

This can be done with BFS (Breadth-First Search) or DFS (Depth-First Search).

The problem can be solved by appropriately implementing above. The complexity is \(O((N+M)\log \max A)\) time.

Sample code (Python 3)

from collections import deque

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    x, y, z = map(int, input().split())
    x, y = x - 1, y - 1
    g[x].append((y, z))
    g[y].append((x, z))

visited = [False] * n
val = [-1] * n

def bfs(start):
    dq = deque([start])
    visited[start] = True
    comp = [start]
    while dq:
        v = dq.popleft()
        for u, w in g[v]:
            if not visited[u]:
                visited[u] = True
                val[u] = val[v] ^ w
                comp.append(u)
                dq.append(u)
            else:
                if val[u] != val[v] ^ w:
                    print("-1")
                    exit()
    return comp

ans = [0] * n
for st in range(n):
    if visited[st]:
        continue
    val[st] = 0
    comp = bfs(st)
    for i in range(30):
        cnt = 0
        for j in comp:
            if val[j] & (1 << i):
                cnt += 1
        if cnt < len(comp) - cnt:
            for j in comp:
                if val[j] & (1 << i):
                    ans[j] |= 1 << i
        else:
            for j in comp:
                if not (val[j] & (1 << i)):
                    ans[j] |= 1 << i
print(*ans)

実装例 (Python3)

import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
import sys

sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    x, y = x - 1, y - 1
    g[x].append((y, z))
    g[y].append((x, z))
visited = [False] * n
val = [-1] * n


q = []


def dfs(v):
    visited[v] = True
    for u, w in g[v]:
        if not visited[u]:
            val[u] = val[v] ^ w
            q.append(u)
            dfs(u)
        else:
            if val[u] != val[v] ^ w:
                print("-1")
                exit()


ans = [0] * n
for st in range(n):
    if visited[st]:
        continue
    val[st] = 0
    q = [st]
    dfs(st)
    for i in range(30):
        cnt = 0
        for j in q:
            if val[j] & (1 << i):
                cnt += 1
        if cnt < len(q) - cnt:
            for j in q:
                if val[j] & (1 << i):
                    ans[j] |= 1 << i
        else:
            for j in q:
                if not val[j] & (1 << i):
                    ans[j] |= 1 << i
print(*ans)