output_description: Print the answer in N lines. In the i-th line, print the color of vertex i
  after the Q operations.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      a_1 b_1
      :
      a_{M} b_{M}
      Q
      v_1 d_1 c_1
      :
      v_{Q} d_{Q} c_{Q}
attempt: for t in range(1):
      graph = {}
      colors = {}
      n, m = list(map(int, input().split()))
      for i in range(m):
          a, b = list(map(int, input().split()))
          if a not in graph:
              graph[a] = [b]
          else:
              graph[a].append(b)
          if b not in graph:
              graph[b] = [a]
          else:
              graph[b].append(a)  # Generating the graph as a dictionary.
          colors[a] = 0
          colors[b] = 0  # Generating a colors dictionary to record color of each vertex.
      for q in range(int(input())):
          v, d, c = list(map(int, input().split()))
          first, sec = [v], []
          colors[v] = c
          for level in range(d):
              for i in first:
                  for j in graph[i]:
                      sec.append(j)
                      colors[j] = c
              first, sec = (
                  sec,
                  [],
              )  # Loop to color all vertices within d distance of given vertex v with color c.
      for i in range(1, n + 1):
          print(colors[i])  # your code goes here
  
problem_description: Statement
  
  Squid loves painting vertices in graphs.
  
  There is a simple undirected graph consisting of N vertices numbered 1 through
  N, and M edges. Initially, all the vertices are painted in color 0. The i-th
  edge bidirectionally connects two vertices a_i and b_i. The length of every
  edge is 1.
  
  Squid performed Q operations on this graph. In the i-th operation, he repaints
  all the vertices within a distance of d_i from vertex v_i, in color c_i.
  
  Find the color of each vertex after the Q operations.
samples: [{"input": "7 7\n    1 2\n    1 3\n    1 4\n    4 5\n    5 6\n    5 7\n    2 3\n    2\n    6 1 1\n    1 2 2", "output": "2\n    2\n    2\n    2\n    2\n    1\n    0\n    \n\nInitially, each vertex is painted in color 0. In the first operation, vertices\n5 and 6 are repainted in color 1. In the second operation, vertices 1, 2, 3, 4\nand 5 are repainted in color 2.\n\n![2ab7e180230b159d42d35ea7e555b3b0.png](https://atcoder.jp/img/agc012/2ab7e180230b159d42d35ea7e555b3b0.png)\n\n* * *"}, {"input": "14 10\n    1 4\n    5 7\n    7 11\n    4 10\n    14 7\n    14 3\n    6 14\n    8 11\n    5 13\n    8 3\n    8\n    8 6 2\n    9 7 85\n    6 9 3\n    6 7 5\n    10 3 1\n    12 9 4\n    9 6 6\n    8 2 3", "output": "1\n    0\n    3\n    1\n    5\n    5\n    3\n    3\n    6\n    1\n    3\n    4\n    5\n    3\n    \n\nThe given graph may not be connected."}]