Problem:
 Score : 700 points    Problem 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.      Constraints  1 ≤ N,M,Q ≤ 10^5  1 ≤ a_i,b_i,v_i ≤ N  a_i ≠ b_i  0 ≤ d_i ≤ 10  1 ≤ c_i ≤10^5  d_i and c_i are all integers.  There are no self-loops or multiple edges in the given graph.       Partial Score  200 points will be awarded for passing the testset satisfying 1 ≤ N,M,Q ≤ 2{,}000 .         Input 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}       Output Print the answer in N lines.
In the i -th line, print the color of vertex i after the Q operations.        Sample Input 1 7 7
1 2
1 3
1 4
4 5
5 6
5 7
2 3
2
6 1 1
1 2 2      Sample Output 1 2
2
2
2
2
1
0  Initially, each vertex is painted in color 0 .
In the first operation, vertices 5 and 6 are repainted in color 1 .
In the second operation, vertices 1 , 2 , 3 , 4 and 5 are repainted in color 2 .         Sample Input 2 14 10
1 4
5 7
7 11
4 10
14 7
14 3
6 14
8 11
5 13
8 3
8
8 6 2
9 7 85
6 9 3
6 7 5
10 3 1
12 9 4
9 6 6
8 2 3      Sample Output 2 1
0
3
1
5
5
3
3
6
1
3
4
5
3  The given graph may not be connected.

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n)]
for a,b in ab:
  a -= 1
  b -= 1
  graph[a].append(b)
  graph[b].append(a)
q = int(input())
query = [list(map(int,input().split())) for i in range(q)]
query = query[::-1]
depth = [-1 for i in range(n)]
color = [0 for i in range(n)]
stack = []
for v,d,c in query:
  v -= 1
  if depth[v] < d:
    stack.append((v,d))
  while stack:
    x,dep = stack.pop()
    if color[x] == 0:
      color[x] = c
    for y in graph[x]:
      if depth[y] < dep-1:
        stack.append((y,dep-1))
        depth[y] = dep-1
print(*color,sep="\n")

Solution (Python):
from collections import deque

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

C = [0] * N
D = [-1] * N
for v, d, c in vdc[::-1] :
  q = deque([(v - 1, d, c)])
  while q :
    cv, cd, cc = q.popleft()
    if D[cv] >= cd :
      continue
    D[cv] = cd
    if C[cv] == 0 :
      C[cv] = cc
    for nv in ab[cv] :
      q.append((nv, cd - 1, cc))

for i in range(N) :
  print(C[i])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

    q=int(input())
    VDC=[None]*q
    for i in range(q):
        v,d,c=map(int,input().split())
        v-=1
        VDC[i]=(v,d,c)
    VDC.reverse()

    dp=[[0]*11 for _ in range(n)]
    ans=[0]*n

    for v,d,c in VDC:
        Q=deque([(v,d)])
        dp[v][d]=1
        while(Q):
            v,d=Q.popleft()
            if(d>0):
                if(not dp[v][d-1]):
                    dp[v][d-1]=1
                    Q.append((v,d-1))
                for nv in E[v]:
                    if(dp[nv][d-1]): continue
                    dp[nv][d-1]=1
                    Q.append((nv,d-1))
            if(ans[v]==0):
                ans[v]=c

    print(*ans,sep='\n')
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

    q=int(input())
    VDC=[None]*q
    for i in range(q):
        v,d,c=map(int,input().split())
        v-=1
        VDC[i]=(v,d,c)
    VDC.reverse()

    dp=[[0]*11 for _ in range(n)]
    ans=[0]*n

    for v,d,c in VDC:
        Q=deque([(v,d)])
        dp[v][d]=1
        while(Q):
            v,d=Q.popleft()
            if(d>0):
                Q.append((v,d-1))
                for nv in E[v]:
                    if(dp[nv][d-1]): continue
                    dp[nv][d-1]=1
                    Q.append((nv,d-1))
            if(ans[v]==0):
                ans[v]=c

    print(*ans,sep='\n')
resolve()

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.readline

N, M = map(int, readline().split())
Edge = [[] for _ in range(N)]

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

Q = int(readline())
VDC = [map(int, readline().split()) for _ in range(Q)]
VDC.reverse()

table = [-1]*N
Col = [[0]*11 for _ in range(N)]
for v, d, c in VDC:
    v -= 1
    if table[v] >= d:
        continue
    Q = deque([(v, d)])
    while Q:
        vn, dn = Q.pop()
        Col[vn][dn] = c
        table[vn] = dn
        for vf in Edge[vn]:
            if table[vf] < dn-1:
                Q.appendleft((vf, dn-1))
Ans = [0]*N
for i in range(N):
    for j in range(11):
        if Col[i][j]:
            Ans[i] = Col[i][j]
            break
print('\n'.join(map(str, Ans)))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(m)]
    edges = [[] for _ in range(n)]
    for a, b in ab:
        edges[a - 1].append(b - 1)
        edges[b - 1].append(a - 1)
    
    q = int(input())
    ans = [0 for _ in range(n)]
    dd = [-1 for _ in range(n)]
    vdc = [tuple(map(int, input().split())) for _ in range(q)]
    for v, d, c in vdc[::-1]:
        if dd[v - 1] >= d:
            
            continue
        
        node = set()
        node.add(v - 1)
        while d >= 0 and len(node) > 0:
            next_node = set()
            for u in node:
                if dd[u] >= d:
                    continue
                dd[u] = d
                if ans[u] == 0:
                    ans[u] = c
                for v in edges[u]:
                    if dd[v] < d - 1:
                        next_node.add(v)
            node = next_node
            d -= 1
    
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(m)]
    edges = [[] for _ in range(n)]
    for a, b in ab:
        edges[a - 1].append(b - 1)
        edges[b - 1].append(a - 1)
    
    q = int(input())
    ans = [0 for _ in range(n)]
    dd = [-1 for _ in range(n)]
    vdc = [tuple(map(int, input().split())) for _ in range(q)]
    for v, d, c in vdc[::-1]:
        if dd[v - 1] >= d:
            
            continue
        
        node = []
        node.append(v - 1)
        while d >= 0 and len(node) > 0:
            next_node = []
            while len(node) > 0:
                u = node.pop()
                if dd[u] >= d:
                    continue
                dd[u] = d
                if ans[u] == 0:
                    ans[u] = c
                for v in edges[u]:
                    if dd[v] < d - 1:
                        next_node.append(v)
            node = next_node
            d -= 1
    
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N, M = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
Q = int(sys.stdin.buffer.readline())
VDC = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]


graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


dp = [[None] * 11 for _ in range(N)]
for i, (v, d, c) in reversed(list(enumerate(VDC))):
    v -= 1
    if not dp[v][d]:
        dp[v][d] = i, c

for d in reversed(range(1, 11)):
    for v in range(N):
        if not dp[v][d]:
            continue
        for u in graph[v] + [v]:
            if not dp[u][d - 1] or (dp[u][d - 1] and dp[u][d - 1][0] < dp[v][d][0]):
                dp[u][d - 1] = dp[v][d]

for v in range(N):
    if dp[v][0]:
        print(dp[v][0][1])
    else:
        print(0)

Solution (Python):
def main():
	n, m, *L = map(int, open(0).read().split())
	AB = L[:2 * m]
	Q = L[2 * m + 1:][::-1]
	G = [[] for _ in range(n)]
	C = [0] * n
	D = [-1] * n
	for a, b in zip(*[iter(AB)] * 2):
		a -= 1
		b -= 1
		G[a] += [b]
		G[b] += [a]
	for c, d, v in zip(*[iter(Q)] * 3):
		if D[v - 1] >= d:
			continue
		D[v - 1] = d
		q = [v - 1]
		while q:
			cur = q.pop()
			dd = D[cur]
			if not C[cur]:
				C[cur] = c
			if not dd:
				continue
			for nxt in G[cur]:
				if D[nxt] >= dd - 1:
					continue
				D[nxt] = dd - 1
				q.append(nxt)
	print("\n".join(map(str, C)))

if __name__=="__main__":
	main()

Solution (Python):
def main():
	n, m, *L = map(int, open(0).read().split())
	AB = L[:2 * m]
	Q = L[2 * m + 1:][::-1]
	G = [[] for _ in range(n)]
	C = [0] * n
	D = [-1] * n
	for a, b in zip(*[iter(AB)] * 2):
		a -= 1
		b -= 1
		G[a] += [b]
		G[b] += [a]
	for c, d, v in zip(*[iter(Q)] * 3):
		if D[v - 1] >= d:
			continue
		D[v - 1] = d
		q = [v - 1]
		while q:
			cur = q.pop()
			dd = D[cur]
			if not C[cur]:
				C[cur] = c
			if not dd:
				continue
			for nxt in G[cur]:
				if D[nxt] >= dd - 1:
					continue
				D[nxt] = dd - 1
				q.append(nxt)
	print("\n".join(map(str, C)))

if __name__=="__main__":
	main()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
Q = int(input())
qs = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    qs.append((v, d, c))
qs.reverse()

seen = [-1] * (N+1)
ans = [0] * (N+1)
for v0, d0, c in qs:
    if d0 > seen[v0]:
        que = deque()
        que.append((v0, d0))
        seen[v0] = d0
        while que:
            v, d = que.popleft()
            if ans[v] == 0:
                ans[v] = c
            if d > 0:
                for u in adj[v]:
                    if d-1 > seen[u]:
                        que.append((u, d-1))
                        seen[u] = d-1

for i in range(1, N+1):
    print(ans[i])

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
Q = int(input())
VDC = [list(map(int, input().split())) for _ in range(Q)]
Ans = [0] * (N+1)
D = [-1] * (N+1)

def dfs(v, d, c):
    if D[v] >= d:
        return
    D[v] = d
    if Ans[v]==0:
        Ans[v] = c
    for u in E[v]:
        dfs(u, d-1, c)

for v, d, c in VDC[::-1]:
    dfs(v, d, c)

print("\n".join(map(str, Ans[1:])))

Solution (Python):
from collections import deque

def main():
    N, M, *L = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(L[:2 * M])] * 2):
        E[a].append(b)
        E[b].append(a)

    colors = [0] * (N + 1)
    visited = [-1] * (N + 1)

    for v, d, c in reversed(tuple(zip(*[iter(L[2 * M + 1:])] * 3))):
        Q = deque([(d, v)])
        while Q:
            cnt, v = Q.popleft()
            if visited[v] >= cnt:
                continue
            if colors[v] == 0:
                colors[v] = c
            visited[v] = cnt
            if cnt > 0:
                Q.extend((cnt - 1, u) for u in E[v] if visited[u] < cnt - 1)

    for c in colors[1:]:
        print(c)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    N, M, *L = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(L[:2 * M])] * 2):
        E[a].append(b)
        E[b].append(a)

    colors = [0] * (N + 1)
    visited = [-1] * (N + 1)

    for v, d, c in reversed(tuple(zip(*[iter(L[2 * M + 1:])] * 3))):
        Q = deque([(d, v)])
        while Q:
            cnt, v = Q.popleft()
            if visited[v] >= cnt:
                continue
            if colors[v] == 0:
                colors[v] = c
            visited[v] = cnt
            if cnt > 0:
                Q.extend((cnt - 1, u) for u in E[v])

    for c in colors[1:]:
        print(c)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N, M, *L = map(int, open(0).read().split())
AB, VDC = L[:2 * M], L[2 * M + 1:]

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

colors = [0] * (N + 1)
visited = [-1] * (N + 1)

for v, d, c in reversed(tuple(zip(*[iter(VDC)] * 3))):
    Q = deque([(d, v)])
    while Q:
        cnt, v = Q.popleft()
        if visited[v] >= cnt:
            continue
        if colors[v] == 0:
            colors[v] = c
        visited[v] = cnt
        if cnt > 0:
            Q.extend((cnt - 1, u) for u in E[v])

for c in colors[1:]:
    print(c)

Solution (Python):
from collections import deque

N, M, *L = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(L[:2 * M])] * 2):
    E[a].append(b)
    E[b].append(a)

colors = [0] * (N + 1)
visited = [-1] * (N + 1)

for v, d, c in reversed(tuple(zip(*[iter(L[2 * M + 1:])] * 3))):
    Q = deque([(d, v)])
    while Q:
        cnt, v = Q.popleft()
        if visited[v] >= cnt:
            continue
        if colors[v] == 0:
            colors[v] = c
        visited[v] = cnt
        if cnt > 0:
            Q.extend((cnt - 1, u) for u in E[v])

for c in colors[1:]:
    print(c)

Solution (Python):
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]
Q = int(input())
VDC = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

color = [0] * (N+1)
visited = [[False] * 11 for _ in range(N+1)]



for v,d,c in VDC[::-1]:
    if visited[v][d]:
        continue
    if color[v] == 0:
        color[v] = c
    for i in range(d+1):
        visited[v][i] = True
    q = [v]
    for t in range(d-1,-1,-1):
        qq = []
        for v in q:
            for w in graph[v]:
                if visited[w][t]:
                    continue
                for i in range(t+1):
                    visited[w][i] = True
                if color[w] == 0:
                    color[w] = c
                qq.append(w)
        q = qq

print('\n'.join(map(str,color[1:])))

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    Q = int(input())
    queries = [None] * Q
    dp = [[-1] * 11 for _ in range(N)]
    for i in range(Q):
        v, d, c = map(int, input().split())
        queries[i] = (v, d, c)
    for i in range(Q)[::-1]:
        v, d, c = queries[i]
        if dp[v-1][d] == -1:
            dp[v-1][d] = i
    for j in range(10)[::-1]:
        for i in range(N):
            dp[i][j] = max(dp[i][j], dp[i][j+1])
            for nxt in adj[i]:
                dp[i][j] = max(dp[i][j], dp[nxt][j+1])
    for i in range(N):
        x = dp[i][0]
        if x == -1:
            print(0)
        else:
            print(queries[x][2])


if __name__ == "__main__":
    main()

Solution (Python):
def dfs(i,v,d,c):
  if dp[v][d]==-1:
    dp[v][d]=i
    if d>0:
      dfs(i,v,d-1,c)
      for u in g[v]:
        dfs(i,u,d-1,c)
  
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q=int(input())
arr=[]
for i in range(q):
  v,d,c=map(int,input().split())
  arr.append((i,v,d,c))
dp=[[-1]*11 for _ in range(n+1)]
for i,v,d,c in arr[::-1]:
  dfs(i,v,d,c)
ans=[]
for i in range(1,n+1):
  if dp[i][0]==-1:
    ans.append(0)
  else:
    ans.append(arr[dp[i][0]][3])
for i in range(n):
  print(ans[i])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n = I()

    return


def B():
    def dfs(d,x,c):
        if d <= dp[x]:
            return
        dp[x] = d
        if not f[x]:
            f[x] = c
        for y in v[x]:
            dfs(d-1,y,c)
    n,m = LI()
    f = [0]*n
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    dp = defaultdict(lambda : -1)
    q = I()
    l = LIR(q)
    l = l[::-1]
    for x,d,c in l:
        x -= 1
        dfs(d,x,c)
    for i in f:
        print(i)
    return


def C():
    n = I()

    return


def D():
    n = I()

    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    B()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        adjL[A-1].append(B-1)
        adjL[B-1].append(A-1)
    Q = int(input())
    querys = []
    for iQ in range(Q):
        v, d, c = map(int, input().split())
        querys.append((iQ, v-1, d, c))

    dp = [[-1]*(11) for _ in range(N)]

    def rec(vNow, d, c, iQ):
        if dp[vNow][d] == -1:
            dp[vNow][d] = iQ
            if d > 0:
                rec(vNow, d-1, c, iQ)
                for v2 in adjL[vNow]:
                    rec(v2, d-1, c, iQ)

    for iQ, v, d, c in reversed(querys):
        rec(v, d, c, iQ)

    anss = [0] * N
    for v in range(N):
        if dp[v][0] != -1:
            anss[v] = querys[dp[v][0]][3]

    print('\n'.join(map(str, anss)))

solve()

Solution (Python):
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
nei =[[i] for i in range(n)]

for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    nei[a].append(b)
    nei[b].append(a)

color = [0 for i in range(n)]
depth = [-1 for i in range(n)]

def paint(v,d,c,pre):
    if d <= depth[v]:
        return
    depth[v] = d
    if color[v] == 0:
        color[v] = c
    if d == 0:
        return
    for next in nei[v]:
        if next == pre:
            continue
        paint(next,d-1,c,v)

q = int(input())
vbc = [list(map(int,input().split())) for i in range(q)][::-1]

for i in range(q):
    paint(vbc[i][0]-1,vbc[i][1],vbc[i][2],-1)
    


for co in color:
    print(co)

Solution (Python):
n, m = map(int, input().split())
adj = [[i] for i in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

dp = [[0 for _ in range(11)] for _ in range(n)]
qs = [0]

q = int(input())
for i in range(q):
	v, d, c = map(int, input().split())
	qs.append(c)
	dp[v-1][d] = i+1

for j in range(10, 0, -1):
	for i in range(n):
		for v in adj[i]:
			dp[v][j-1] = max(dp[v][j-1], dp[i][j])

for i in range(n):
	print(qs[dp[i][0]])

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
adj = [[i] for i in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

dp = [[0 for _ in range(11)] for _ in range(n)]
qs = [0]

q = int(input())
for i in range(q):
	v, d, c = map(int, input().split())
	qs.append(c)
	dp[v-1][d] = i+1

for j in range(10, 0, -1):
	for i in range(n):
		for v in adj[i]:
			dp[v][j-1] = max(dp[v][j-1], dp[i][j])

for i in range(n):
	print(qs[dp[i][0]])

Solution (Python):
n, m  = map(int, input().split())
g     = {}
used  = {i:[False for _ in range(11)] for i in range(n)}
color     = [0  for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []

for _ in range(q):
    node, dis, col = map(int, input().split())
    Q.append([node-1, dis, col])
Q = Q[::-1]

def bfs(now, dist, col):
    if dist < 0:
        return
    
    if used[now][dist]:
        return
 
    used[now][dist] = True
    
    if not color[now]:
        color[now] = col
 
    if now in g:
        for x in g[now]:
            bfs(x, dist - 1, col)
            
for node, dis, col in Q:
    bfs(node, dis, col)

for x in color:
    print(x)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
N,M=map(int,input().split())
table=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    table[a].append(b)
    table[b].append(a)
Q=int(input())
X=[[int(i) for i in input().split()] for i in range(Q)]
color=[0]*Q
dp=[[-1]*N for i in range(11)]
for i in range(Q-1,-1,-1):
    v, d, c=X[i]
    v=v-1
    color[i]=c
    dp[d][v]=max(dp[d][v],i)

for d in range(10,0,-1):
    for x in range(N):
        for y in table[x]:
            dp[d-1][y]=max(dp[d][x],dp[d-1][y])
for i in range(N):
    s=-1
    for d in range(11):
        s=max(s,dp[d][i])
    if s==-1:
        print(0)
    else:
        print(color[s])

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
n,m=map(int, input().split())
Edges=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int, input().split())
    Edges[a-1].append(b-1)
    Edges[b-1].append(a-1)
q=int(input())
Q=[list(map(int,input().split())) for _ in range(q)][::-1]
Visited=[-1]*n
Color=[0]*n
que=deque()
for v,d,c in Q:
    v-=1
    if Visited[v]>=d:
        continue
    Visited[v]=d
    que.append((v,d))
    while que:
        v,d=que.popleft()
        if not Color[v]:
            Color[v]=c
        d-=1
        for i in Edges[v]:
            if Visited[i]>=d:
                continue
            Visited[i]=d
            que.append((i,d))
print(*Color,sep="\n")

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] for _ in range(n)]

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

q = int(input())

query = [list(map(int, input().split())) for _ in range(q)]

color = [0] * n
depth = [-1] * n

def dfs(node, dist, col, pre_node):
    if dist <= depth[node]:
        return
    depth[node] = dist
    if color[node] == 0:
        color[node] = col
    if dist == 0:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist-1, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, d, c, -1)

for co in color:
    print(co)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

N,M = map(int,input().split())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
Q = int(input())
qs = [tuple(map(int,input().split())) for i in range(Q)]

es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)

cs = [0] * N
depth = [-1] * N

def rec(v,d,c,pv):
    if d <= depth[v]: return
    depth[v] = d
    if cs[v]==0:
        cs[v] = c
    if d==0: return
    for to in es[v]:
        if to==pv: continue
        rec(to,d-1,c,v)

for v,d,c in qs[::-1]:
    rec(v-1,d,c,-1)

print(*cs, sep='\n')

Solution (Python):
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
Q=int(input())
v=[0 for i in range(Q)]
d=[0 for i in range(Q)]
c=[0 for i in range(Q)]
for i in range(Q):
    v[-i-1],d[-i-1],c[-i-1]=map(int,input().split());v[-i-1]-=1
q=deque()
color=[0 for i in range(N)]
dp=[-1 for i in range(N)]
for t in range(Q):
    if dp[v[t]]>=d[t]:
        continue
    dp[v[t]]=d[t]
    q.append((v[t],d[t]))
    while(q):
        vv,dd=q.popleft()
        if color[vv]==0:
            color[vv]=c[t]
        dd-=1
        for y in G[vv]:
            if dp[y]>=dd:
                continue
            dp[y]=dd
            q.append((y,dd))
for line in color:
    print(line)

Solution (Python):
N,M=map(int,input().split())
E=[]
for i in range(M):
  a,b=map(int,input().split())
  E.append((a-1,b-1))
Q=int(input())
dp=[[-1]*11 for i in range(N)]
C=[]
for i in range(Q):
  v,d,c=map(int,input().split())
  dp[v-1][d]=i
  C.append(c)
for d in range(1,11)[::-1]:
  for n in range(N):
    dp[n][d-1]=max(dp[n][d],dp[n][d-1])
  for a,b in E:
    dp[a][d-1]=max(dp[a][d-1],dp[b][d])
    dp[b][d-1]=max(dp[b][d-1],dp[a][d])
for i in range(N):
  if dp[i][0]>=0:
    print(C[dp[i][0]])
  else:
    print(0)

Solution (Python):
n,m = map(int,input().split())
p = [list(map(int,input().split())) for i in range(m)]
q = int(input())
v = [list(map(int,input().split())) for i in range(q)]
v = v[::-1]
l = [[] for i in range(n+1)]
for pi in p:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
mita = [-1]*(n+1)
tugi = [set() for i in range(n+1)]
iro = [0] *(n+1)
def dfs(x,y,z):
  if iro[x] == 0:
    iro[x] = z
  if mita[x] >=y:
    return
  for i in l[x]:
    if y-1>=0:
      dfs(i,y-1,z)
  mita[x] = y
for ch in v:
  dfs(ch[0],ch[1],ch[2])
for i in range(1,n+1):
  print(iro[i])

Solution (Python):





"""
agc012 C
"""


n, m = map(int, input().split())

graph = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

q = int(input())
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        for i in range(d+1):
            if dp[v][i] == -1:
                dp[v][i] = t
        if d > 0:
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

for i in range(1, n+1):
    print(col[dp[i][0]+1])

Solution (Python):





"""
agc012 C
"""


n, m = map(int, input().split())

graph = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

q = int(input())
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        dp[v][d] = t
        if d > 0:
            updatedp(v, t, d-1)
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

for i in range(1, n+1):
    print(col[dp[i][0]+1])

Solution (Python):





"""
agc012 C
"""

from collections import defaultdict

n, m = map(int, input().split())

graph = defaultdict(list)
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

q = int(input())
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        dp[v][d] = t
        if d > 0:
            updatedp(v, t, d-1)
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

for i in range(1, n+1):
    print(col[dp[i][0]+1])

Solution (Python):
n,m = (int(i) for i in input().split())
x,y,dp = [[] for i in range(n)],[],[[0,-1] for i in range(n)]
for i in range(m):
	a,b = (int(i)-1 for i in input().split())
	x[a].append(b)
	x[b].append(a)
q = int(input())
for i in range(q):
	v,d,c = (int(i) for i in input().split())
	y.append((v-1,d,c))
def f(v,d,c):
	z,z2 = dp[v]
	if d>z2:
		if z: dp[v] = z,d
		else: dp[v] = c,d
		if d:
			for i in x[v]: f(i,d-1,c)
for i,j,k in y[::-1]: f(i,j,k)
for i in dp: print(i[0])

Solution (Python):
n, m=map(int, raw_input().split())
adj=[[] for i in range(n+1)]
for i in range(m):
	a, b=map(int, raw_input().split())
	adj[a].append(b)
	adj[b].append(a)
q=input()
bucket=[[] for i in range(11)]
for i in range(q):
	v, d, c=map(int, raw_input().split())
	bucket[d].append((v, c, i))
result=[0]*(n+1)
time=[-1]*(n+1)
for i in range(10, -1, -1):
	new_result=result[:]
	new_time=time[:]
	for cur in range(n+1):
		for to in adj[cur]:
			if new_time[to]<time[cur]:
				new_time[to]=time[cur]
				new_result[to]=result[cur]
	result=new_result
	time=new_time
	for cur, color, t in bucket[i]:
		if time[cur]<t:
			time[cur]=t
			result[cur]=color
for i in range(1, n+1):
	print result[i]
print