题目描述

Squid喜欢给图中的顶点上色。

有一个简单无向图，由$N$个编号为$1$到$N$的顶点和$M$条边组成。初始时，所有顶点都被涂成颜色$0$。第$i$条边双向连接两个顶点$a_i$和$b_i$。每条边的长度为$1$。

Squid在该图上进行了$Q$次操作。在第$i$次操作中，他将距离顶点$v_i$距离为$d_i$以内的所有顶点涂成颜色$c_i$。

找出在经过$Q$次操作后，每个顶点的颜色。

约束条件

• $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$和$c_i$均为整数。
• 给定图中不存在自环或重边。

局部得分

• 对满足 $1 ≤ N,M,Q ≤ 2{,}000$ 的测试集，将获得额外 $200$ 分。

输入

从标准输入读入输入数据，具体格式如下：

$N$ $M$ $a_1$ $b_1$ $:$ $a_{M}$ $b_{M}$ $Q$ $v_1$ $d_1$ $c_1$ $:$ $v_{Q}$ $d_{Q}$ $c_{Q}$

输出

按顺序输出结果。在第$i$行，输出经过$Q$次操作后顶点$i$的颜色。

示例输入 1

7 7
1 2
1 3
1 4
4 5
5 6
5 7
2 3
2
6 1 1
1 2 2

示例输出 1

2
2
2
2
2
1
0

初始时，每个顶点的颜色都是$0$。第一次操作中，顶点$5$和$6$被涂成颜色$1$。第二次操作中，顶点$1$、$2$、$3$、$4$和$5$被涂成颜色$2$。

示例输入 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

示例输出 2

1
0
3
1
5
5
3
3
6
1
3
4
5
3

给定的图可能不是连通的。