stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn=(int)1e5+10;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

struct node{

	int to,nxt;

}ed[maxn<<1];

int head[maxn],cnt;

void addedge(int u,int v){

	ed[cnt].to=v;

	ed[cnt].nxt=head[u];

	head[u]=cnt++;

}

int st[maxn],d[maxn],c[maxn],mark[maxn],dis[maxn],col[maxn];

vector<int>vx;

int main()

{

	int n,m;

	memset(head,-1,sizeof(head));

	memset(mark,-1,sizeof(mark));

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		int u,v;

		u=read(),v=read();

		addedge(u,v);

		addedge(v,u);

	}

	int q;

	scanf("%d",&q);

	for(int i=1;i<=q;i++){

		st[i]=read();d[i]=read();c[i]=read();

	}

	for(int i=q;i>=1;i--){

		if(d[i]<=mark[st[i]])continue;

		queue<int>q;

		q.push(st[i]);

		while(!q.empty()){

			int u=q.front();q.pop();

			if(dis[u]+mark[u]>=d[i])continue;

			if(col[u]==0)col[u]=c[i];	

			mark[u]=d[i]-dis[u];

			for(int j=head[u];~j;j=ed[j].nxt){

				int v=ed[j].to;

				if(dis[v]==0&&v!=st[i]&&dis[u]<d[i]){

					dis[v]=dis[u]+1;

					vx.push_back(v);

					q.push(v);

				}

			}

		}

		for(int j=0;j<vx.size();j++)dis[vx[j]]=0;

		vx.clear();

	}

	for(int i=1;i<=n;i++)printf("%d\n",col[i]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8300503338996221x):
#include<bits/stdc++.h>

#define rint register int

using namespace std;

int read(){

    int s=0,f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}

    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();

    return f?s:-s;

}

int n,m,Q,s[100010],mmp[100010],cl[100010];

int col[100010],vis[100010][11],hxcAK[100010];

int tot,head[100010],ver[200010],nxt[200010];

void add(int x,int y){

    nxt[++tot]=head[x]; ver[tot]=y;

    head[x]=tot;

}

void dfs(int x,int dis,int cr){

	if(!hxcAK[x]) col[x]=cr,hxcAK[x]=1;

	vis[x][dis]=1;

	if(dis==0) return;

	for(rint i=head[x];i;i=nxt[i]){

		int y=ver[i];

		if(vis[y][dis-1]) continue;

		vis[y][dis-1]=1;

		dfs(y,dis-1,cr);

	}

}

int main(){

    n=read(); m=read();

    for(rint i=1,x,y;i<=m;++i){

        x=read(); y=read();

        add(x,y); add(y,x);

    }

    Q=read();

    for(rint i=1;i<=Q;++i)

        s[i]=read(),mmp[i]=read(),cl[i]=read();

    for(rint i=Q;i;--i) dfs(s[i],mmp[i],cl[i]);

    for(rint i=1;i<=n;++i) printf("%d\n",col[i]);

    return 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



*/
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long

vector<int>q[200000];

int color[200000];

int flag[200000];

int n,m;

int v[200000],d[200000],c[200000];

void dfs(int x,int cnt,int c)

{

   if(!color[x])

       color[x]=c;

   if(flag[x]>=cnt)

       return;

   if(cnt==0)

       return;

   flag[x]=cnt;

   for(int i=0;i<q[x].size();i++)

       dfs(q[x][i],cnt-1,c);

}

int main()

{

    cin>>n>>m;

    for(int i=1;i<=m;i++)

    {

        int x,y;

        cin>>x>>y;

        q[x].push_back(y);

        q[y].push_back(x);

    }

    int q;

    cin>>q;

    for(int i=1;i<=q;i++)

       cin>>v[i]>>d[i]>>c[i];

    for(int i=q;i>=1;i--)

        dfs(v[i],d[i],c[i]);

    for(int i=1;i<=n;i++)

        cout<<color[i]<<endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 6.5467454278004x):
#include<bits/stdc++.h>

#define rint register int

using namespace std;

int read(){

    int s=0,f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}

    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();

    return f?s:-s;

}

int n,m,Q,s[100010],mmp[100010],cl[100010];

int col[100010],vis[100010][11],hxcAK[100010];

int tot,head[100010],ver[200010],nxt[200010];

void add(int x,int y){

    nxt[++tot]=head[x]; ver[tot]=y;

    head[x]=tot;

}

void dfs(int x,int dis,int cr){

	if(!hxcAK[x]) col[x]=cr,hxcAK[x]=1;

	vis[x][dis]=1;

	if(dis==0) return;

	for(rint i=head[x];i;i=nxt[i]){

		int y=ver[i];

		if(vis[y][dis-1]) continue;

		vis[y][dis-1]=1;

		dfs(y,dis-1,cr);

	}

}

int main(){

    n=read(); m=read();

    for(rint i=1,x,y;i<=m;++i){

        x=read(); y=read();

        add(x,y); add(y,x);

    }

    Q=read();

    for(rint i=1;i<=Q;++i)

        s[i]=read(),mmp[i]=read(),cl[i]=read();

    for(rint i=Q;i;--i) dfs(s[i],mmp[i],cl[i]);

    for(rint i=1;i<=n;++i) printf("%d\n",col[i]);

    return 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



*/
// Slower C++ solution:
#include<cstdio>

#include<algorithm>

#include<cstring>

#define maxn 200050

#define add(u,v) (to[++top]=head[u],head[u]=top,w[top]=v)

#define For(x) for(int h=head[x],o=w[h];h;o=w[h=to[h]])

using namespace std;

int n,m,to[maxn],head[maxn],w[maxn],u,v,top;

int a[maxn],b[maxn],c[maxn],co[maxn],r[maxn],q,i;

void dfs(int x,int rg,int col)

{

	if (rg<=r[x]||rg<=0) return;

	r[x]=rg; 

	if (co[x]==0) co[x]=col;

	For(x) dfs(o,rg-1,col);

}

int main()

{

	scanf("%d%d",&n,&m);

	while (m--)

	{

		scanf("%d%d",&u,&v);

		add(u,v); add(v,u);

    }

    scanf("%d",&q);

    for (i=1;i<=q;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);

    memset(co,0,sizeof(co)); memset(r,0,sizeof(r));

    for (i=q;i>=1;i--) dfs(a[i],b[i]+1,c[i]);

    for (i=1;i<=n;i++) printf("%d\n",co[i]);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8157281936363967x):
#include<bits/stdc++.h>

#define rint register int

using namespace std;

int read(){

    int s=0,f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}

    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();

    return f?s:-s;

}

int n,m,Q,s[100010],mmp[100010],cl[100010];

int col[100010],vis[100010][11],hxcAK[100010];

int tot,head[100010],ver[200010],nxt[200010];

void add(int x,int y){

    nxt[++tot]=head[x]; ver[tot]=y;

    head[x]=tot;

}

void dfs(int x,int dis,int cr){

	if(!hxcAK[x]) col[x]=cr,hxcAK[x]=1;

	vis[x][dis]=1;

	if(dis==0) return;

	for(rint i=head[x];i;i=nxt[i]){

		int y=ver[i];

		if(vis[y][dis-1]) continue;

		vis[y][dis-1]=1;

		dfs(y,dis-1,cr);

	}

}

int main(){

    n=read(); m=read();

    for(rint i=1,x,y;i<=m;++i){

        x=read(); y=read();

        add(x,y); add(y,x);

    }

    Q=read();

    for(rint i=1;i<=Q;++i)

        s[i]=read(),mmp[i]=read(),cl[i]=read();

    for(rint i=Q;i;--i) dfs(s[i],mmp[i],cl[i]);

    for(rint i=1;i<=n;++i) printf("%d\n",col[i]);

    return 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



*/
// Slower C++ solution:
#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#define N 100010

using namespace std;

struct Dis{

	int x,z;

};

queue<Dis>Q;

int a[N],c[N],d[N],e[N],f[N],num,h[N],n,m,p,q,t,col;

bool bo[N];

struct Edge{

	int p,q,n;

}b[N*2];

void ljb(int p,int q){

	b[++num].n=h[p];

	h[p]=num;

	b[num].p=p;

	b[num].q=q;

}

void Bfs(){

	int x,y,z;

	while(!Q.empty()){

		x=Q.front().x; z=Q.front().z; Q.pop(); 

//		printf("%d %d\n",x,z);

		if(!f[x])f[x]=col;

		e[x]=max(e[x],z);

		if(z==0)continue;

		for(int i=h[x];i!=0;i=b[i].n){

			y=b[i].q;

			if(e[y]<z-1)Q.push((Dis){y,z-1});

		}

	}

}

int main(){

	memset(e,-1,sizeof(e));

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		scanf("%d%d",&p,&q);

		ljb(p,q);

		ljb(q,p);

	}

	scanf("%d",&t);

	for(int i=1;i<=t;i++)scanf("%d%d%d",&a[i],&d[i],&c[i]);

	for(int i=t;i>=1;i--){

		if(e[a[i]]>=d[i])continue;

		col=c[i];

		Q.push((Dis){a[i],d[i]});

		Bfs();

	}

//	for(int i=1;i<=n;i++)printf("%d %d\n",i,e[i]);

	for(int i=1;i<=n;i++)printf("%d\n",f[i]);

}

// Faster C++ solution for the same problem (measured speedup: 1.4222600989569052x):
#include<bits/stdc++.h>

#define rint register int

using namespace std;

int read(){

    int s=0,f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}

    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();

    return f?s:-s;

}

int n,m,Q,s[100010],mmp[100010],cl[100010];

int col[100010],vis[100010][11],hxcAK[100010];

int tot,head[100010],ver[200010],nxt[200010];

void add(int x,int y){

    nxt[++tot]=head[x]; ver[tot]=y;

    head[x]=tot;

}

void dfs(int x,int dis,int cr){

	if(!hxcAK[x]) col[x]=cr,hxcAK[x]=1;

	vis[x][dis]=1;

	if(dis==0) return;

	for(rint i=head[x];i;i=nxt[i]){

		int y=ver[i];

		if(vis[y][dis-1]) continue;

		vis[y][dis-1]=1;

		dfs(y,dis-1,cr);

	}

}

int main(){

    n=read(); m=read();

    for(rint i=1,x,y;i<=m;++i){

        x=read(); y=read();

        add(x,y); add(y,x);

    }

    Q=read();

    for(rint i=1;i<=Q;++i)

        s[i]=read(),mmp[i]=read(),cl[i]=read();

    for(rint i=Q;i;--i) dfs(s[i],mmp[i],cl[i]);

    for(rint i=1;i<=n;++i) printf("%d\n",col[i]);

    return 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



*/
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int q[101000],H=0,T=0;

int col[101000],d[101000];

int h[101000],nxt[201000],to[201000],K=0;

int V[101000],D[101000],C[101000];

void ins(int u,int v){nxt[++K]=h[u];h[u]=K;to[K]=v;}

int main()

{

	int n,m;scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++)

	{

		int a,b;scanf("%d%d",&a,&b);

		ins(a,b);ins(b,a);

	}

	int Q;scanf("%d",&Q);

	for(int i=1;i<=Q;i++)scanf("%d%d%d",&V[i],&D[i],&C[i]);

	memset(d,-1,sizeof(d));

	for(int i=Q;i>=1;i--)

	{

		if(D[i]>d[V[i]])

		{

			H=T=0;d[V[i]]=D[i];q[T++]=V[i];

			while(H<T)

			{

				int x=q[H++];if(!col[x])col[x]=C[i];

				for(int j=h[x];j;j=nxt[j])

				{

					if(d[to[j]]<d[x]-1)

					{

						d[to[j]]=d[x]-1;

						q[T++]=to[j];

					}

				}

			}

		}

	}

	for(int i=1;i<=n;i++)printf("%d\n",col[i]);return 0;

 } 

// Faster C++ solution for the same problem (measured speedup: 1.4213400829964526x):
#include<bits/stdc++.h>

#define rint register int

using namespace std;

int read(){

    int s=0,f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}

    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();

    return f?s:-s;

}

int n,m,Q,s[100010],mmp[100010],cl[100010];

int col[100010],vis[100010][11],hxcAK[100010];

int tot,head[100010],ver[200010],nxt[200010];

void add(int x,int y){

    nxt[++tot]=head[x]; ver[tot]=y;

    head[x]=tot;

}

void dfs(int x,int dis,int cr){

	if(!hxcAK[x]) col[x]=cr,hxcAK[x]=1;

	vis[x][dis]=1;

	if(dis==0) return;

	for(rint i=head[x];i;i=nxt[i]){

		int y=ver[i];

		if(vis[y][dis-1]) continue;

		vis[y][dis-1]=1;

		dfs(y,dis-1,cr);

	}

}

int main(){

    n=read(); m=read();

    for(rint i=1,x,y;i<=m;++i){

        x=read(); y=read();

        add(x,y); add(y,x);

    }

    Q=read();

    for(rint i=1;i<=Q;++i)

        s[i]=read(),mmp[i]=read(),cl[i]=read();

    for(rint i=Q;i;--i) dfs(s[i],mmp[i],cl[i]);

    for(rint i=1;i<=n;++i) printf("%d\n",col[i]);

    return 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



*/
// Slower C++ solution:
#include<bits/stdc++.h>

#include<cmath>

#include<math.h>

#include<ctype.h>

#include<algorithm>

#include<string.h>

#include<stdio.h>

#include<iostream>

#define f(i,n) for (int i=0;i<(n);i++)

#define f1(i,n) for (int i=1;i<=(n);i++)

#define pb push_back

#define ms(a) memset((a),0,sizeof(a))

#define ll long long

#define vi vector<int>

#define mp make_pair

#define die assert(fasle)

#define pii pair<int,int>

#define INF 0x3f3f3f3f

#define N (int)1e5+5

using namespace std;

int n, m, q;

vi g[N];

int v[N], d[N], c[N];

int ans[N];

int lft;

int mds[N];

void dfs(int vv, int dd, int cc) {

	if (!lft) return;

	if (dd < 0) return;

	if (!ans[vv])ans[vv] = cc;

	if (dd <= mds[vv]) return;

	mds[vv] = dd;

	//printf("%d %d %d\n", vv, dd, cc);

	for (int i = 0; i < g[vv].size(); i ++) {

		if (!g[vv][i])lft --;

		dfs(g[vv][i], dd-1, cc);

	}

}

int main() {

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= m; i ++) {

		int x, y;

		scanf("%d%d", &x, &y);

		g[x].pb(y);

		g[y].pb(x);

	}

	scanf("%d", &q);

	for (int i = 1; i <= q; i ++) {

		scanf("%d%d%d", &v[i], &d[i], &c[i]);

	}

	for (int i = 1; i <= n; i ++) {

		mds[i] = -1;

	}

	lft = n;

	for (int i = q; i >= 1; i --) {

		//puts("");

		dfs(v[i], d[i], c[i]);

//		for (int j = 1; j <= n; j ++) {

//			printf("%d ", ans[j]);

//		}

//		puts("");

//		printf("%d\n", lft);

//		puts("");

		if (!lft) break;

	}

	for (int i = 1; i <= n; i ++) {

		printf("%d\n", ans[i]);

	}

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.5666451524346843x):
#include<bits/stdc++.h>

#define rint register int

using namespace std;

int read(){

    int s=0,f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}

    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();

    return f?s:-s;

}

int n,m,Q,s[100010],mmp[100010],cl[100010];

int col[100010],vis[100010][11],hxcAK[100010];

int tot,head[100010],ver[200010],nxt[200010];

void add(int x,int y){

    nxt[++tot]=head[x]; ver[tot]=y;

    head[x]=tot;

}

void dfs(int x,int dis,int cr){

	if(!hxcAK[x]) col[x]=cr,hxcAK[x]=1;

	vis[x][dis]=1;

	if(dis==0) return;

	for(rint i=head[x];i;i=nxt[i]){

		int y=ver[i];

		if(vis[y][dis-1]) continue;

		vis[y][dis-1]=1;

		dfs(y,dis-1,cr);

	}

}

int main(){

    n=read(); m=read();

    for(rint i=1,x,y;i<=m;++i){

        x=read(); y=read();

        add(x,y); add(y,x);

    }

    Q=read();

    for(rint i=1;i<=Q;++i)

        s[i]=read(),mmp[i]=read(),cl[i]=read();

    for(rint i=Q;i;--i) dfs(s[i],mmp[i],cl[i]);

    for(rint i=1;i<=n;++i) printf("%d\n",col[i]);

    return 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



*/
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

int t[100100], us[100100][20];

vector <int> g[100100];

void func(int v, int d, int c)

{

    if(us[v][d])

        return;

    us[v][d] = 1;

    if(d == 0)

    {

        t[v] = c;

        return;

    }

    func(v, d - 1, c);

    for(int i = 0; i < g[v].size(); ++i)

        func(g[v][i], d - 1, c);

}



int main()

{

    int n, m, i, x, y, q, z;

    vector <pair <pair <int, int>, int> > v;



    cin >> n >> m;

    for(i = 0; i < m; ++i)

    {

        cin >> x >> y;

        g[x].push_back(y);

        g[y].push_back(x);

    }

    cin >> q;

    for(i = 0; i < q; ++i)

    {

        cin >> x >> y >> z;

        v.push_back(make_pair(make_pair(x, y), z));

    }

    while(!v.empty())

    {

        func(v.back().first.first, v.back().first.second, v.back().second);

        v.pop_back();

    }

    for(i = 1; i <= n; ++i)

        cout << t[i] << endl;



return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.600928319954511x):
/*   三玖天下第一！！！  */

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5,maxd=10;

int n,m,Q,_39[maxn+5]={},lin[maxn+5]={},len=0;

bool vis[maxn+5][maxd+5]={};

struct edge{int y,next;}e[(maxn<<1)+5];

inline void insert(int xx,int yy){e[++len]={yy,lin[xx]};lin[xx]=len;}

inline int dread()

{

	int x=0;bool f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');

	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);

	return f?x:-x;

}

struct operation

{

	int v,d,c;

	inline void read(){v=dread();d=dread();c=dread();}

}opt[maxn+5];

void color(int point,int dis,int c)

{

	if(vis[point][dis]) return;else for(int i=0;i<=dis;i++)vis[point][i]=1;

	if(!_39[point]) _39[point]=c;

	if(!dis) return;

	for(int i=lin[point];i;i=e[i].next) color(e[i].y,dis-1,c);

}

inline void Kaslana()

{

	n=dread();m=dread();

	for(int i=1,u,v;i<=m;i++) insert(u=dread(),v=dread()),insert(v,u);

	Q=dread();

	for(int i=1;i<=Q;i++) opt[i].read();

}

inline void Raiden()

{

	for(int i=Q;i>=1;i--) color(opt[i].v,opt[i].d,opt[i].c);

}

inline void Zaychik()

{

	for(int i=1;i<=n;i++) printf("%d\n",_39[i]);

}

int main()

{

    Kaslana(),Raiden(),Zaychik();return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <memory.h>

#include <vector>

using namespace std;

const int maxn = 200005;

struct Query{

    int v, d, c;

}q[maxn];

int n, m, Q;

vector<int> G[maxn];

bool vis[maxn][15];

int color[maxn];



void solve(int v, int d, int c){

    if(vis[v][d]) return;

    if(color[v] == 0)    color[v] = c;

    if(d <= 0) return;



    for(int i = 0; i < G[v].size(); i++)

    {

        solve(G[v][i], d-1, c);

    }

    vis[v][d] = 1;



}

int main(){

//freopen("input.txt", "r", stdin);

    scanf("%d %d", &n, &m);

    memset(color, 0, sizeof(color));

    memset(vis, false, sizeof(vis));

    int a, b;

    for(int i = 0; i < m; i++)

    {

        scanf("%d %d", &a, &b);

        G[a].push_back(b);

        G[b].push_back(a);

    }

    scanf("%d", &Q);

    for(int i = 0; i < Q; i++)

    {

        scanf("%d %d %d", &q[i].v, &q[i].d, &q[i].c);

    }

    for(int i = Q-1; i >= 0; i--)

       solve(q[i].v, q[i].d, q[i].c);

    for(int i = 1; i <= n; i++)

        printf("%d\n", color[i]);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 10.81571640325505x):
/*   三玖天下第一！！！  */

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5,maxd=10;

int n,m,Q,_39[maxn+5]={},lin[maxn+5]={},len=0;

bool vis[maxn+5][maxd+5]={};

struct edge{int y,next;}e[(maxn<<1)+5];

inline void insert(int xx,int yy){e[++len]={yy,lin[xx]};lin[xx]=len;}

inline int dread()

{

	int x=0;bool f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');

	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);

	return f?x:-x;

}

struct operation

{

	int v,d,c;

	inline void read(){v=dread();d=dread();c=dread();}

}opt[maxn+5];

void color(int point,int dis,int c)

{

	if(vis[point][dis]) return;else for(int i=0;i<=dis;i++)vis[point][i]=1;

	if(!_39[point]) _39[point]=c;

	if(!dis) return;

	for(int i=lin[point];i;i=e[i].next) color(e[i].y,dis-1,c);

}

inline void Kaslana()

{

	n=dread();m=dread();

	for(int i=1,u,v;i<=m;i++) insert(u=dread(),v=dread()),insert(v,u);

	Q=dread();

	for(int i=1;i<=Q;i++) opt[i].read();

}

inline void Raiden()

{

	for(int i=Q;i>=1;i--) color(opt[i].v,opt[i].d,opt[i].c);

}

inline void Zaychik()

{

	for(int i=1;i<=n;i++) printf("%d\n",_39[i]);

}

int main()

{

    Kaslana(),Raiden(),Zaychik();return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define maxn 100100

#define lson root << 1

#define rson root << 1 | 1

#define lent (t[root].r - t[root].l + 1)

#define lenl (t[lson].r - t[lson].l + 1)

#define lenr (t[rson].r - t[rson].l + 1)

#define N 1111

#define eps 1e-6

#define pi acos(-1.0)

#define e exp(1.0)

using namespace std;

const int mod = 1e9 + 7;

typedef long long ll;

typedef unsigned long long ull;

vector<int> g[maxn];

int vis[maxn], col[maxn];

tuple<int, int, int> op[maxn];

void dfs(int v, int d, int c)

{

	if (vis[v] >= d)

		return;

	vis[v] = d;

	if (!col[v])

		col[v] = c;

	if (d)

	{

		int sz = g[v].size();

		for (int i = 0; i < sz; i++)

			dfs(g[v][i], d - 1, c);

	}

}

int main()

{

	int n, m, q;

	while (~scanf("%d%d", &n, &m))

	{

		for (int i = 1; i <= n; i++)

			g[i].clear();

		fill(vis, vis + n + 1, -1);

		fill(col, col + n + 1, 0);

		while (m--)

		{

			int u, v;

			scanf("%d%d", &u, &v);

			g[u].push_back(v);

			g[v].push_back(u);

		}

		scanf("%d", &q);

		for (int i = 0; i < q; i++)

		{

			int v, d, c;

			scanf("%d%d%d", &v, &d, &c);

			op[i] = tuple<int, int, int>(v, d, c);

		}

		for (int i = q - 1; i >= 0; i--)

		{

			int v, d, c;

			tie(v, d, c) = op[i];

			dfs(v, d, c);

		}

		for (int i = 1; i <= n; i++)

			printf("%d\n", col[i]);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.572407275426669x):
/*   三玖天下第一！！！  */

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5,maxd=10;

int n,m,Q,_39[maxn+5]={},lin[maxn+5]={},len=0;

bool vis[maxn+5][maxd+5]={};

struct edge{int y,next;}e[(maxn<<1)+5];

inline void insert(int xx,int yy){e[++len]={yy,lin[xx]};lin[xx]=len;}

inline int dread()

{

	int x=0;bool f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');

	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);

	return f?x:-x;

}

struct operation

{

	int v,d,c;

	inline void read(){v=dread();d=dread();c=dread();}

}opt[maxn+5];

void color(int point,int dis,int c)

{

	if(vis[point][dis]) return;else for(int i=0;i<=dis;i++)vis[point][i]=1;

	if(!_39[point]) _39[point]=c;

	if(!dis) return;

	for(int i=lin[point];i;i=e[i].next) color(e[i].y,dis-1,c);

}

inline void Kaslana()

{

	n=dread();m=dread();

	for(int i=1,u,v;i<=m;i++) insert(u=dread(),v=dread()),insert(v,u);

	Q=dread();

	for(int i=1;i<=Q;i++) opt[i].read();

}

inline void Raiden()

{

	for(int i=Q;i>=1;i--) color(opt[i].v,opt[i].d,opt[i].c);

}

inline void Zaychik()

{

	for(int i=1;i<=n;i++) printf("%d\n",_39[i]);

}

int main()

{

    Kaslana(),Raiden(),Zaychik();return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn=(int)1e5+10;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

struct node{

	int to,nxt;

}ed[maxn<<1];

int head[maxn],cnt;

void addedge(int u,int v){

	ed[cnt].to=v;

	ed[cnt].nxt=head[u];

	head[u]=cnt++;

}

int st[maxn],d[maxn],c[maxn],mark[maxn],dis[maxn],col[maxn];

vector<int>vx;

int main()

{

	int n,m;

	memset(head,-1,sizeof(head));

	memset(mark,-1,sizeof(mark));

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		int u,v;

		u=read(),v=read();

		addedge(u,v);

		addedge(v,u);

	}

	int q;

	scanf("%d",&q);

	for(int i=1;i<=q;i++){

		st[i]=read();d[i]=read();c[i]=read();

	}

	for(int i=q;i>=1;i--){

		if(d[i]<=mark[st[i]])continue;

		queue<int>q;

		q.push(st[i]);

		while(!q.empty()){

			int u=q.front();q.pop();

			if(dis[u]+mark[u]>=d[i])continue;

			if(col[u]==0)col[u]=c[i];	

			mark[u]=d[i]-dis[u];

			for(int j=head[u];~j;j=ed[j].nxt){

				int v=ed[j].to;

				if(dis[v]==0&&v!=st[i]&&dis[u]<d[i]){

					dis[v]=dis[u]+1;

					vx.push_back(v);

					q.push(v);

				}

			}

		}

		for(int j=0;j<vx.size();j++)dis[vx[j]]=0;

		vx.clear();

	}

	for(int i=1;i<=n;i++)printf("%d\n",col[i]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8318810267914192x):
/*   三玖天下第一！！！  */

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5,maxd=10;

int n,m,Q,_39[maxn+5]={},lin[maxn+5]={},len=0;

bool vis[maxn+5][maxd+5]={};

struct edge{int y,next;}e[(maxn<<1)+5];

inline void insert(int xx,int yy){e[++len]={yy,lin[xx]};lin[xx]=len;}

inline int dread()

{

	int x=0;bool f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');

	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);

	return f?x:-x;

}

struct operation

{

	int v,d,c;

	inline void read(){v=dread();d=dread();c=dread();}

}opt[maxn+5];

void color(int point,int dis,int c)

{

	if(vis[point][dis]) return;else for(int i=0;i<=dis;i++)vis[point][i]=1;

	if(!_39[point]) _39[point]=c;

	if(!dis) return;

	for(int i=lin[point];i;i=e[i].next) color(e[i].y,dis-1,c);

}

inline void Kaslana()

{

	n=dread();m=dread();

	for(int i=1,u,v;i<=m;i++) insert(u=dread(),v=dread()),insert(v,u);

	Q=dread();

	for(int i=1;i<=Q;i++) opt[i].read();

}

inline void Raiden()

{

	for(int i=Q;i>=1;i--) color(opt[i].v,opt[i].d,opt[i].c);

}

inline void Zaychik()

{

	for(int i=1;i<=n;i++) printf("%d\n",_39[i]);

}

int main()

{

    Kaslana(),Raiden(),Zaychik();return 0;

}