题目描述

给一个 $n$ 个点 $m$ 条边的无向图，有 $q$ 次操作。第 $i$ 次操作给出 $v,d,c$，把所有到点 $v$ 的距离不超过 $d$ 的点都染上颜色 $c$。可以覆盖之前染上的颜色。

问最后每个点的颜色。

$1\le n, m, q, c \le 10^5$，$0\le d \le 10$。

输入格式

第一行为 $n,m$。

然后输入 $m$ 行，每行为一条无向边的两端。保证没有重边和自环。

接下来一行为一个数 $q$。

最后 $q$ 行每一行三个数 $v,d,c$。

输出格式

总共 $n$ 行，其中第 $i$ 行表示点 $i$ 最后的颜色。

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

2
2
2
2
2
1
0

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

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