# AGC 12 B - Splatter Painting ( BFS )

B: Splatter Painting - AtCoder Grand Contest 012 | AtCoder

1≦N,M,Q≦1e5
1≦ai,bi,vi≦N
ai≠bi
0≦di≦10
1≦ci≦1e5
di,ci いずれも整数

O( 10 * N ) / O( N )

```from collections import deque

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

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

Q = int( input() )
V = []
D = []
C = []
for qi in range( Q ):
v, d, c = 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 ] )
```