Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def solve():
    N,M = map(int,input().strip().split())
    ans = [0]*(N+1)
    g = dict()
    for i in range(M):
      ai,bi = map(int,input().strip().split())
      if ai in g:
        g[ai].append(bi)
      else:
        g[ai] = [bi]
      if bi in g:
        g[bi].append(ai)
      else:
        g[bi] = [ai]

    Q = int(input())
    for i in range(Q):
      v,d,c = map(int,input().strip().split())
      ans[v]=c
      done={v}
      queue = set(g.get(v,list()))
      for j in range(d):
        n_queue = set()
        for idx in queue:
          ans[idx]=c
          done.add(idx)
          for k in g.get(idx,list()):
            if k not in done:
              n_queue.add(k)
        queue = n_queue
    for i in range(N):
      print(ans[i+1])


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
input = sys.stdin.readline

INF = 10**14

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

maxd = 0
Q = int(input())
Query = []
Color = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    if d > maxd:
        maxd = d
    Query.append((v-1, d))
    Color.append(c)

Query = Query[::-1]
Color = Color[::-1]

dp = [[INF]*(maxd+1) for _ in range(N)]
for i, (v, d) in enumerate(Query):
    if i < dp[v][d]:
        dp[v][d] = i

for d in reversed(range(maxd)):
    for v in range(N):
        if dp[v][d+1] < dp[v][d]:
            dp[v][d] = dp[v][d+1]
        for nv in graph[v]:
            if dp[v][d+1] < dp[nv][d]:
                dp[nv][d] = dp[v][d+1]

for v in range(N):
    seq = dp[v][0]
    if seq == INF:
        print(0)
    else:
        print(Color[seq])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def solve():
    N,M = map(int,input().strip().split())
    ans = [0]*(N+1)
    g = dict()
    for i in range(M):
      ai,bi = map(int,input().strip().split())
      if ai in g:
        g[ai].append(bi)
      else:
        g[ai] = [bi]
      if bi in g:
        g[bi].append(ai)
      else:
        g[bi] = [ai]

    Q = int(input())
    for i in range(Q):
      v,d,c = map(int,input().strip().split())
      ans[v]=c
      queue = set(g.get(v,list()))
      for j in range(d):
        n_queue = set()
        done = set()
        for idx in queue:
          ans[idx]=c
          if idx not in done:
            n_queue.update(set(g.get(idx,list())))
            done.add(idx)
        queue = n_queue
    for i in range(N):
      print(ans[i+1])


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
input = sys.stdin.readline

INF = 10**14

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

maxd = 0
Q = int(input())
Query = []
Color = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    if d > maxd:
        maxd = d
    Query.append((v-1, d))
    Color.append(c)

Query = Query[::-1]
Color = Color[::-1]

dp = [[INF]*(maxd+1) for _ in range(N)]
for i, (v, d) in enumerate(Query):
    if i < dp[v][d]:
        dp[v][d] = i

for d in reversed(range(maxd)):
    for v in range(N):
        if dp[v][d+1] < dp[v][d]:
            dp[v][d] = dp[v][d+1]
        for nv in graph[v]:
            if dp[v][d+1] < dp[nv][d]:
                dp[nv][d] = dp[v][d+1]

for v in range(N):
    seq = dp[v][0]
    if seq == INF:
        print(0)
    else:
        print(Color[seq])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def solve():
    N,M = map(int,input().strip().split())
    ans = [0]*(N+1)
    g = dict()
    for i in range(M):
      ai,bi = map(int,input().strip().split())
      if ai in g:
        g[ai].append(bi)
      else:
        g[ai] = [bi]
      if bi in g:
        g[bi].append(ai)
      else:
        g[bi] = [ai]

    Q = int(input())
    for i in range(Q):
      v,d,c = map(int,input().strip().split())
      ans[v]=c
      done = {v}
      queue = set(g.get(v,list()))
      for j in range(d):
        n_queue = set()
        for idx in queue:
          ans[idx]=c
          if idx not in done:
            n_queue.update(set(g.get(idx,list())))
        queue = n_queue
    for i in range(N):
      print(ans[i+1])


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
input = sys.stdin.readline

INF = 10**14

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

maxd = 0
Q = int(input())
Query = []
Color = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    if d > maxd:
        maxd = d
    Query.append((v-1, d))
    Color.append(c)

Query = Query[::-1]
Color = Color[::-1]

dp = [[INF]*(maxd+1) for _ in range(N)]
for i, (v, d) in enumerate(Query):
    if i < dp[v][d]:
        dp[v][d] = i

for d in reversed(range(maxd)):
    for v in range(N):
        if dp[v][d+1] < dp[v][d]:
            dp[v][d] = dp[v][d+1]
        for nv in graph[v]:
            if dp[v][d+1] < dp[nv][d]:
                dp[nv][d] = dp[v][d+1]

for v in range(N):
    seq = dp[v][0]
    if seq == INF:
        print(0)
    else:
        print(Color[seq])