该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一张 $n$ 个点 $m$ 条边的无向图，所有边的长度都是 $1$。每个点会有一个颜色，初始时每个点的颜色编号是 $0$。

会有 $q$ 个操作来对该图进行染色，每个操作会有三个参数 $v,d,c$ 表示将距离 $v$ 点不超过 $d$ 的所有点颜色变成 $c$。此处，两点之间的距离定义为它们之间的最短路上的边数。如果两点无法到达，认为他们的距离为正无穷。

• 显然， $v$ 自身到自身的最短路为 $0$。

现求 $q$ 个操作依次完成后每个点的颜色。

输入格式

第一行两个整数 $n$ 和 $m$，分别表示图的点数和边数。

接下来 $m$ 行，每行两个整数 $a_i$ 和 $b_i$，表示两者之间有一条连边。

接下来一个整数 $q$，表示操作个数。

最后 $q$ 行，每行三个整数 $v_i,d_i,c_i$，表示一次染色操作，意义如题目描述。

输出格式

输出 $n$ 行，每行一个整数，第 $i$ 行输出的是 $q$ 次操作后第 $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

说明/提示

对于 $20\%$ 的数据，满足 $1\leq n,m,q \leq 100$ 。

对于 $50\%$ 的数据，满足 $1\leq n,q \leq 2000$。

对于 $100\%$ 的数据，满足 $1\leq n,m,q,c_i \leq 2*10^5$ ，$1 \leq d_i \leq 20$，$1 \leq a_i,b_i,v_i\leq n$。

本题数据，不保证图连通，也不保证不存在重边。