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

题目背景

知周所众，一场合格的思维比赛一定要有一道不算特别难的算法题......

题目描述

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

会有 $q$ 个操作来对该图进行染色，每个操作会有三个参数 $v,d,c$ 表示将距离 $v$ 点不超过 $d$ 的所有点颜色变成 $c$。

• $v$ 自身到自身的最短路为 $0$。
• 两点之间的距离定义为它们之间的最短路上的边数

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

输入格式

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

接下来 $m$ 行，每行两个整数 $x$ 和 $y$ 和 $z$，表示两者之间有一条连边，边权为 $z$。

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

后 $q$ 行，每行三个整数 $v,d,c$，表示一次染色操作，意义如题目描述。

输出格式

输出 $n$ 行，每行一个整数，第 $i$ 行输出的是 $q$ 次操作后第 $i$ 个点的颜色。

样例 #1

样例输入 #1

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

样例输出 #1

2
2
2
2
2
1
0

提示

对于 $100\%$ 的数据，满足 $1\leq n,m,q,c \leq 2000$，$1 \leq d \leq 20$，$1 \leq x,y,v\leq n$，$z = 1$。

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