CodeEff/ECCO huggingface dataset:
# Original solution
from collections import deque
N=int(eval(input()))
tree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
paths=[]
for i in range(N-1):
    a,b=list(map(int,input().split()))
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    paths.append([a-1,b-1,i,0])
paths=sorted(paths,key=lambda x:x[1])
paths.sort(key=lambda x:x[0])
#print(paths)
v=0
d=deque()
d.append(v)
seen=[0]*N
col=[-1]*N
path=[]
dirtree = [[] for _ in range(N)]
while len(d)>0:
    v=d.popleft()
    seen[v]=1
    for j in tree[v]:
        if seen[j]==0:
            d.append(j)
            dirtree[v].append(j)
#print(dirtree)
v=0
d.append(v)
col[v]=0
while len(d)>0:
    v=d.popleft()
    seen[v]=0
    c=0
    for j in dirtree[v]:
        if seen[j]==1:
            d.append(j)
            c=c+1
            if c==col[v]:
                c=c+1
                path.append([min(j,v),max(j,v),c])
            else:
                path.append([min(j, v), max(j, v), c])
            col[j]=c
    path = sorted(path, key=lambda x: x[1])
    path.sort(key=lambda x: x[0])
    #print(path)
    #input()
for i in range(N-1):
    paths[i][3]=path[i][2]
paths.sort(key=lambda x:x[2])
path.sort(key=lambda x:x[2],reverse=True)
print((path[0][2]))
for i in range(N-1):
    print((paths[i][3]))

# Optimized solution
from collections import deque
N=int(eval(input()))
tree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
paths=[]
for i in range(N-1):
    a,b=list(map(int,input().split()))
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    paths.append([a-1,b-1,i,0])
paths=sorted(paths,key=lambda x:x[1])
paths.sort(key=lambda x:x[0])
#print(paths)
v=0
d=deque()
d.append(v)
seen=[0]*N
col=[-1]*N
path=[]
dirtree = [[] for _ in range(N)]
while len(d)>0:
    v=d.popleft()
    seen[v]=1
    for j in tree[v]:
        if seen[j]==0:
            d.append(j)
            dirtree[v].append(j)
#print(dirtree)
v=0
d.append(v)
col[v]=0
while len(d)>0:
    v=d.popleft()
    seen[v]=0
    c=0
    for j in dirtree[v]:
        if seen[j]==1:
            d.append(j)
            c=c+1
            if c==col[v]:
                c=c+1
                path.append([min(j,v),max(j,v),c])
            else:
                path.append([min(j, v), max(j, v), c])
            col[j]=c
path = sorted(path, key=lambda x: x[1])
path.sort(key=lambda x: x[0])
    #print(path)
    #input()
for i in range(N-1):
    paths[i][3]=path[i][2]
paths.sort(key=lambda x:x[2])
path.sort(key=lambda x:x[2],reverse=True)
print((path[0][2]))
for i in range(N-1):
    print((paths[i][3]))
# Original solution
from collections import deque
N=int(eval(input()))
G=[[] for n in range(N)]
E=[]
color_map={}
for n in range(N-1):
    a,b=list(map(int,input().split()))
    E.append((a-1,b-1))
    color_map[(a-1,b-1)]=0
    G[a-1].append(b-1)
    G[b-1].append(a-1)
deg=[len(v) for v in G]
K=max(deg)
Q=deque([0])
X=[]

while Q:
    v=Q.popleft()
    X.append(v)
    for u in set(G[v])-set(X):
        Q.append(u)
    if v!=0:
        p=(set(X)&set(G[v])).pop()
        colors=set(range(1,K+1))
        for q in G[p]:
            p1,q1=min(p,q),max(p,q)
            colors-={color_map[(p1,q1)]}
        a,b=min(p,v),max(p,v)
        color_map[(a,b)]=colors.pop()
print(K)
for edge in E:
    print((color_map[edge]))


# Optimized solution
from collections import deque

N=int(eval(input()))
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=list(map(int,input().split()))
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
K=max([len(v) for v in G])

P=[-1]*N
Q=[0]
X=[]
count=0
while Q:
    v=Q.pop()
    X.append(v)
    for u in G[v]:
        if u==P[v]:
            continue
        P[u]=v
        Q.append(u)

C={}
for v in X:
    color=0
    try:
        p_color=C[tuple(sorted((v,P[v])))]
    except:
        p_color=-1
    for u in G[v]:
        if u==P[v]:
            continue
        if color==p_color:
            color+=1
        C[tuple(sorted((u,v)))]=color
        color+=1

print(K)
for e in E:
    print((C[e]+1))
# Original solution
from collections import deque

N=int(eval(input()))
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=list(map(int,input().split()))
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
K=max([len(v) for v in G])

P=[-1]*N
Q=[0]
X=[]
count=0
while Q:
    v=Q.pop()
    X.append(v)
    for u in G[v]:
        if u==P[v]:
            continue
        P[u]=v
        Q.append(u)

C={}
for v in X:
    color=0
    try:
        p_color=C[tuple(sorted((v,P[v])))]
    except:
        p_color=-1
    for u in G[v]:
        if u==P[v]:
            continue
        if color==p_color:
            color+=1
        C[tuple(sorted((u,v)))]=color
        color+=1

print(K)
for e in E:
    print((C[e]+1))


# Optimized solution
N=int(eval(input()))
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=list(map(int,input().split()))
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
K=max([len(v) for v in G])

P=[-1]*N
Q=[0]
X=[]
count=0
while Q:
    v=Q.pop()
    X.append(v)
    for u in G[v]:
        if u==P[v]:
            continue
        P[u]=v
        Q.append(u)

C={}
for v in X:
    color=0
    try:
        p_color=C[min(v,P[v]),max(v,P[v])]
    except:
        p_color=-1
    for u in G[v]:
        if u==P[v]:
            continue
        if color==p_color:
            color+=1
        C[min(u,v),max(u,v)]=color
        color+=1

print(K)
for e in E:
    print((C[e]+1))
# Original solution
n, m = list(map(int, input().split()))

g = [[i] for i in range(n)]

for _ in range(m):
    u, v = [int(x) - 1 for x in input().split()]
    g[u].append(v)
    g[v].append(u)

q = int(eval(input()))
c = [None] * q
dp = [[-1 for j in range(n)] for i in range(11)]
for i in range(q):
    v, d, c[i] = list(map(int, input().split()))
    dp[d][v - 1] = i
 
for i in reversed(list(range(1, 11))):
    dp[i - 1] = [max(dp[i - 1][u], max(dp[i][v] for v in g[u])) for u in range(n)]

for i in range(n):
    if dp[0][i] == -1:
        print('0')
    else:
        print((c[dp[0][i]]))

# Optimized solution
n, m = list(map(int, input().split()))

g = [[i] for i in range(n)]

for _ in range(m):
    u, v = [int(x) - 1 for x in input().split()]
    g[u].append(v)
    g[v].append(u)

q = eval(input())
c = [None] * q
dp = [[-1 for j in range(n)] for i in range(11)]
for i in range(q):
    v, d, c[i] = list(map(int, input().split()))
    dp[d][v - 1] = i
 
for i in reversed(list(range(1, 11))):
    dp[i - 1] = [max(dp[i - 1][u], max(dp[i][v] for v in g[u])) for u in range(n)]

for i in range(n):
    if dp[0][i] == -1:
        print('0')
    else:
        print((c[dp[0][i]]))
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

def size(x):
    return -par[find(x)]
  
n, m = map(int, readline().split())
par = [-1]*n
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    unite(u,v)
    
q = int(readline())
chk = []
for i in range(q):
  V,D,C = map(int,readline().split())
  chk.append((V,D,C))
  
from collections import deque
ans = [0]*n
cnt = [0]*n

def bfs(s,col,d,f,ss):
  global end
  que = deque()
  que.append((s,1,col))
  if ans[s] == 0:
    ans[s] = col
    cnt[f] += 1
  while que:
      now,p,col = que.popleft()
      if cnt[f] == ss:
        break
      for i in g[now]:
          if p <= d and ans[i] == 0:
            ans[i] = col
            cnt[f] += 1
            end += 1
            if cnt[f] == ss:
              break
          if p < d:
            que.append((i,p+1,col))

end = 0
for i in chk[::-1]:
  vv,d,cc = i
  f = find(vv-1)
  ss = size(f)
  if end == n:
    break
  if cnt[f] == ss:
    continue
  bfs(vv-1,cc,d,f,ss)
    
print(*ans, sep='\n')


# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(4100000)
  
n,m = list(map(int, readline().split()))
g = [[]*n for i in range(n)]
for i in range(m):
    u,v = list(map(int,readline().split()))
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
q = int(readline())
chk = []
for i in range(q):
  V,D,C = list(map(int,readline().split()))
  chk.append((V,D,C))
  

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

def f(v,d,c):
  if memo[v][d] != 0:
    return
  else:
    memo[v][d] = c
    if d > 0:
      f(v,d-1,c)
      for nxt in g[v]:
        f(nxt,d-1,c)
    else:
      return

for V,D,C in chk[::-1]:
    f(V-1,D,C)

for v in range(n):
    print((memo[v][0]))
# Original solution
inf = 100
N, M = list(map(int, input().split()))
WF = [[inf]*N for _ in range(N)]
for _ in range(M):
	a, b = list(map(int, input().split()))
	WF[a-1][b-1] = 1
	WF[b-1][a-1] = 1
for i in range(N):
	WF[i][i] = 0
for k in range(N):
	for i in range(N):
		for j in range(N):
			WF[i][j] = min(WF[i][j], WF[i][k]+WF[k][j])
C = [0]*N
Q = int(eval(input()))
for _ in range(Q):
	v, d, c = list(map(int, input().split()))
	for i in range(N):
		if WF[v-1][i] <= d:
			C[i] = c

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

# Optimized solution
inf = 100
N, M = list(map(int, input().split()))
G = [[set([j]) for i in range(11)] for j in range(N)]
for _ in range(M):
	a, b = list(map(int, input().split()))
	G[a-1][1].add(b-1)
	G[b-1][1].add(a-1) 

for i in range(N):
	for d in range(1,11):
		for j in G[i][d-1]:
			G[i][d] |= G[j][1]

C = [0]*N
Q = int(eval(input()))
for _ in range(Q):
	v, d, c = list(map(int, input().split()))
	for i in G[v-1][d]:
		C[i] = c

for i in range(N):
	print((C[i]))
# Original solution
N, M = list(map(int, input().split()))
G = [[set([j]) for i in range(11)] for j in range(N)]
for _ in range(M):
	a, b = list(map(int, input().split()))
	G[a-1][1].add(b-1)
	G[b-1][1].add(a-1) 

for i in range(N):
	if len(G[i][1]) == 1:
		continue
	for d in range(1,11):
		for j in G[i][d-1]:
			G[i][d] |= G[j][1]
			if len(G[i][d]) == N:
				break

C = [0]*N
Q = int(eval(input()))
for _ in range(Q):
	v, d, c = list(map(int, input().split()))
	for i in G[v-1][d]:
		C[i] = c

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

# Optimized solution
N, M = list(map(int, input().split()))
G = [[set([j]) for i in range(11)] for j in range(N)]
for _ in range(M):
	a, b = list(map(int, input().split()))
	G[a-1][1].add(b-1)
	G[b-1][1].add(a-1) 

for i in range(N):
	if len(G[i][1]) == 1:
		continue
	for d in range(1,11):
		G[i][d] |= G[i][d-1]
		for j in G[i][d-1]:
			G[i][d] |= G[j][1]
			if len(G[i][d]) == N:
				break

C = [0]*N
Q = int(eval(input()))
for _ in range(Q):
	v, d, c = list(map(int, input().split()))
	for i in G[v-1][d]:
		C[i] = c

for i in range(N):
	print((C[i]))
# Original solution
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = list(map(int, input().split()))
e = dd(list)

for _ in range(M):
  u, v = list(map(int, input().split()))
  e[u].append(v)
  e[v].append(u)

res = [set() for _ in range(N + 1)]
Q = int(eval(input()))
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = list(map(int, input().split()))
  qd[i] = d
  qc[i] = c
  res[v].add(i)
#print(qc)

def clean():
  global res
  for i in range(1, N + 1):
    a = sorted(res[i], reverse = True)
    d = -1
    for j in range(len(a)):
      x = a[j]
      if qd[x] <= d: res[i].discard(x)
      d = max(d, qd[x])
clean()
for t in range(10):
  tres = [set() | s for s in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for z in res[x]:
        if qd[z] > t: tres[y].add(z)
  res = tres
  #clean()
#print(res)

for r in res[1: ]:
  if len(r): print((qc[max(r)]))
  else: print((0))


# Optimized solution
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = list(map(int, input().split()))
e = dd(list)

for _ in range(M):
  u, v = list(map(int, input().split()))
  e[u].append(v)
  e[v].append(u)
mxd = 0
res = [set() for _ in range(N + 1)]
Q = int(eval(input()))
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = list(map(int, input().split()))
  qd[i] = d
  qc[i] = c
  res[v].add(i)
  mxd = max(mxd, d)
#print(qc)

def clean():
  global res
  for i in range(1, N + 1):
    a = sorted(res[i], reverse = True)
    d = -1
    for j in range(len(a)):
      x = a[j]
      if qd[x] <= d: res[i].discard(x)
      d = max(d, qd[x])
clean()
for t in range(mxd):
  tres = [set() | s for s in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for z in res[x]:
        if qd[z] > t: tres[y].add(z)
  res = tres
  clean()
#print(res)

for r in res[1: ]:
  if len(r): print((qc[max(r)]))
  else: print((0))
# Original solution
import collections

n,m=list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=list(map(int,input().split()))
  g[a].append(b)
  g[b].append(a)
q=int(eval(input()))
arr=[list(map(int,input().split())) for _ in range(q)]
color=[0]*(n+1)
for i in range(q):
  v,d,c=arr[i]
  tmp=0
  tq=collections.deque()
  tq.append((v,0,c))
  checked=[0]*(n+1)
  checked[v]=1
  color[v]=c
  while 1:
    if len(tq)==0:
      break
    tv,td,tc=tq.popleft()
    if td>=d:
      break
    for u in g[tv]:
      if checked[u]==0:
        checked[u]=1
        color[u]=tc
        tq.append((u,td+1,tc))
for i in range(1,n+1):
  print((color[i]))

# Optimized solution
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=list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=list(map(int,input().split()))
  g[a].append(b)
  g[b].append(a)
q=int(eval(input()))
arr=[]
for i in range(q):
  v,d,c=list(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]))
# Original solution
import queue

N, M = list(map( int, input().split() ))

G = [ [] for i in range( N ) ]
for i in range( M ):
  u, v = list(map( int, input().split() ))
  G[ u - 1 ].append( v - 1 )
  G[ v - 1 ].append( u - 1 )

Q = int( eval(input()) )
V = []
D = []
C = []
for qi in range( Q ):
  v, d, c = list(map( int, input().split() ))
  V.append( v - 1 )
  D.append( d )
  C.append( c )

vis = [ -1 for i in range( N ) ]
col = [ 0 for i in range( N ) ]
for qi in range( Q - 1, -1, -1 ):
  if D[ qi ] <= vis[ V[ qi ] ]: continue # 影響力不足
  que = queue.Queue()
  vis[ V[ qi ] ] = D[ qi ]
  que.put( ( D[ qi ], V[ qi ] ) )
  if col[ V[ qi ] ] == 0:
    col[ V[ qi ] ] = C[ qi ]
  while not que.empty():
    d, u = que.get()
    if d == 0: continue
    for v in G[ u ]:
      if vis[ v ] >= d - 1: continue
      vis[ v ] = d - 1
      que.put( ( d - 1, v ) )
      if col[ v ] == 0:
        col[ v ] = C[ qi ]

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


# Optimized solution
from collections import deque

N, M = list(map( int, input().split() ))

G = [ [] for i in range( N ) ]
for i in range( M ):
  u, v = list(map( int, input().split() ))
  G[ u - 1 ].append( v - 1 )
  G[ v - 1 ].append( u - 1 )

Q = int( eval(input()) )
V = []
D = []
C = []
for qi in range( Q ):
  v, d, c = list(map( int, input().split() ))
  V.append( v - 1 )
  D.append( d )
  C.append( c )

vis = [ -1 for i in range( N ) ]
col = [ 0 for i in range( N ) ]
for qi in range( Q - 1, -1, -1 ):
  if D[ qi ] <= vis[ V[ qi ] ]: continue # 影響力不足
  que = deque()
  vis[ V[ qi ] ] = D[ qi ]
  que.append( ( D[ qi ], V[ qi ] ) )
  if col[ V[ qi ] ] == 0:
    col[ V[ qi ] ] = C[ qi ]
  while len( que ):
    d, u = que.popleft()
    if d == 0: continue
    for v in G[ u ]:
      if vis[ v ] >= d - 1: continue
      vis[ v ] = d - 1
      que.append( ( d - 1, v ) )
      if col[ v ] == 0:
        col[ v ] = C[ qi ]

for i in range( N ):
  print(( col[ i ] ))
# Original solution
from collections import deque
N,M=list(map(int,input().split()))
G=[[] for i in range(N)]
for i in range(M):
  a,b=list(map(int,input().split()))
  G[a-1].append(b-1)
  G[b-1].append(a-1)
Q=int(eval(input()))
Colors=[0]*N
dp=[[False]*11 for i in range(N)]
def BFS(v,d,c):
  global dp
  for i in range(d+1):
    dp[v][i]=True
  stack=deque([(v,d)])
  global Colors
  while stack:
    n,m=stack.popleft()
    if m<0:
      break
    if Colors[n]==0:
      Colors[n]=c
    for u in G[n]:
      if not dp[u][m]:
        stack.append((u,m-1))
        for i in range(m):
          dp[u][i]=True
q=[list(map(int,input().split())) for i in range(Q)]
for i in q[::-1]:
  v,d,c=i
  BFS(v-1,d,c)
for c in Colors:
  print(c)


# Optimized solution
N,M=list(map(int,input().split()))
E=[]
for i in range(M):
  a,b=list(map(int,input().split()))
  E.append((a-1,b-1))
Q=int(eval(input()))
dp=[[-1]*11 for i in range(N)]
C=[]
for i in range(Q):
  v,d,c=list(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))
# Original solution
# -*- encoding: utf-8 -*-
N,M = list(map(int, input().split()))
C=[]
for i in range(N):
    C.append(0)
AB=[]
for i in range(M):
    AB.append(list(map(int, input().split())))
nextnodes=[]
for i in range(N):
    nextnodes.append([])
for ab in AB:
    #print("%d,%d,%d" % (N, ab[0], ab[1]))
    nextnodes[ab[0]-1].append(ab[1])
    nextnodes[ab[1]-1].append(ab[0])

Q = int(eval(input()))
VDC=[]
for i in range(Q):
    VDC.append(list(map(int, input().split())))
for i in range(Q):
    vdc=VDC[i]
    current = []
    next = []
    v=vdc[0]
    d=vdc[1]
    c=vdc[2]
    C[v-1] = c
    #print("i: %d, dist: 0, n: %d, c: %d" % (i, v, c))
    current.extend(nextnodes[v-1])
    for dist in range(d):
        if len(current) == 0:
            break
        for n in current:
            C[n-1] = c
            #print("i: %d, dist: %d, n: %d, c: %d" % (i, dist+1, n, c))
            next.extend(nextnodes[n-1])
        current = next
        next = []
for i in C:
    print(i)


# Optimized solution
# -*- encoding: utf-8 -*-
N,M = list(map(int, input().split()))
C=[]
for i in range(N):
    C.append(0)
AB=[]
for i in range(M):
    AB.append(list(map(int, input().split())))
nextnodes=[]
for i in range(N):
    nextnodes.append([])
for ab in AB:
    #print("%d,%d,%d" % (N, ab[0], ab[1]))
    nextnodes[ab[0]-1].append(ab[1])
    nextnodes[ab[1]-1].append(ab[0])

Q = int(eval(input()))
VDC=[]
for i in range(Q):
    VDC.append(list(map(int, input().split())))
for i in range(Q):
    vdc=VDC[i]
    current = []
    next = []
    done = set()
    v=vdc[0]
    d=vdc[1]
    c=vdc[2]
    C[v-1] = c
    #print("i: %d, dist: 0, n: %d, c: %d" % (i, v, c))
    current.extend(nextnodes[v-1])
    done.add(v)
    for dist in range(d):
        if len(current) == 0:
            break
        for n in current:
            if n in done:
                continue
            C[n-1] = c
            #print("i: %d, dist: %d, n: %d, c: %d" % (i, dist+1, n, c))
            next.extend(nextnodes[n-1])
            done.add(n)
        current = next
        next = []
for i in C:
    print(i)
# Original solution
def recClr(v,d,c):
    if clr[v-1]==0:
        clr[v-1]=c
#        print "recClr",v,d,c
    if d>0:
        if v in ab:
            for b in ab[v]:
                recClr(b,d-1,c)


N,M=list(map(int,input().split()))
ab={}
for i in range(M):
    a,b=list(map(int,input().split()))
    if a in ab:
        ab[a].append(b)
    else:
        ab[a]=[b]
    if b in ab:
        ab[b].append(a)
    else:
        ab[b]=[a]
#print ab


clr=[0]*N

Q=eval(input())
op=[]
for i in range(Q):
    v,d,c=list(map(int,input().split()))
    op.append((v,d,c))
op.reverse()
for v,d,c in op:
    recClr(v,d,c)
#print clr   

for i in clr:
    print(i)


# Optimized solution
def recClr(v,d,c):
#    print "recClr",v,d,c
    if visited[v-1] >= d:
        return
    else:
        visited[v-1]=d
    if clr[v-1]==0:
        clr[v-1]=c
    if d>0:
        if v in ab:
            for b in ab[v]:
                recClr(b,d-1,c)


N,M=list(map(int,input().split()))
ab={}
for i in range(M):
    a,b=list(map(int,input().split()))
    if a in ab:
        ab[a].append(b)
    else:
        ab[a]=[b]
    if b in ab:
        ab[b].append(a)
    else:
        ab[b]=[a]
#print ab


clr=[0]*N
visited=[-1]*N

Q=eval(input())
op=[]
for i in range(Q):
    v,d,c=list(map(int,input().split()))
    op.append((v,d,c))
op.reverse()
for v,d,c in op:
    recClr(v,d,c)
#print clr   

for i in clr:
    print(i)
# Original solution
from queue import deque


def dijkstra(s, d):
    queue = deque([(0, s)])
    paint = set()
    while queue:
        cost, v = queue.popleft()
        if cost > d:
            break
        paint.add(v)
        queue.extend((cost + 1, u) for u in links[v] if u not in paint)
    return paint


n, m = list(map(int, input().split()))
links = [None] + [set() for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    links[a].add(b)
    links[b].add(a)

q = int(eval(input()))
queries = [list(map(int, input().split())) for _ in range(q)]
painted = set()
colors = [0] * (n + 1)
while queries:
    v, d, c = queries.pop()
    paint = dijkstra(v, d) - painted
    for i in paint:
        colors[i] = c
    painted |= paint

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


# Optimized solution
from queue import deque


def paint(s, d, c):
    queue = deque([(d, s)])
    while queue:
        remains, v = queue.popleft()
        if painted[v] >= remains:
            continue
        if colors[v] == 0:
            colors[v] = c
        painted[v] = remains
        if remains:
            queue.extend((remains - 1, u) for u in links[v])


n, m = list(map(int, input().split()))
links = [None] + [set() for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    links[a].add(b)
    links[b].add(a)

q = int(eval(input()))
queries = [list(map(int, input().split())) for _ in range(q)]
colors = [0] * (n + 1)
painted = [-1] * (n + 1)
while queries:
    paint(*queries.pop())

for c in colors[1:]:
    print(c)
# Original solution
n, m = list(map(int, input().split()))
node = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = list(map(int, input().split()))
    node[a].append(b)
    node[b].append(a)

q = int(eval(input()))
node_color = [0 for _ in range(n + 1)]
for j in range(q):
    v, d, c = list(map(int, input().split()))

    now = [v]
    paint = {v}
    for dist in range(d):
        buff = []
        now = list(set(now))
        for k in now:
            paint |= set(node[k])
            buff.extend(node[k])
        now = buff

    for l in paint:
        node_color[l] = c

for m in range(n):
    print((node_color[m + 1]))


# Optimized solution
n, m = list(map(int, input().split()))
node = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = list(map(int, input().split()))
    node[a].append(b)
    node[b].append(a)

q = int(eval(input()))
node_color = [0 for _ in range(n + 1)]
vdc = [list(map(int, input().split())) for _ in range(q)]

vdc = vdc[::-1]
painted = set()
visited = [[0] * 11 for _ in range(n + 1)]


def dfs(now, dist, color):
    if dist < 0:
        return
    if visited[now][dist]:
        return

    visited[now][dist] += 1
    if not node_color[now]:
        node_color[now] = color

    for x in node[now]:
        dfs(x, dist - 1, color)


for i in vdc:
    v, d, c = i
    dfs(v, d, c)

for m in range(n):
    print((node_color[m + 1]))