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

using namespace std;



const int N = 1e5 + 10;



vector <int> G[N];

int rec[N], color[N], ver[N], d[N], c[N];



void dfs(int x, int dist, int col){

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

	if (~rec[x] && dist <= rec[x]) return;

	rec[x] = dist;

	if (dist == 0) return;

	for (int i = 0; i < G[x].size(); i++) dfs(G[x][i], dist - 1, col);

}



int main(){

	int n, m, q, u, v;

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

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

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

		G[u].push_back(v);

		G[v].push_back(u);

	}

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

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

	scanf("%d",&q);

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

	for (int i = q; i >= 1; i--) dfs(ver[i], d[i], c[i]);

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

	return 0;

}

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

using namespace std;

const int maxn=101000;



struct edge{

	int to,nxt;

}e[maxn<<1];

int head[maxn],tot,n,m,q,dis[maxn],col[maxn];

void add(int x,int y)

{

	e[++tot].to=y;

	e[tot].nxt=head[x];

	head[x]=tot;

}



struct opte{

	int p,d,c;

}opt[maxn];



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

{

	if(dis[x]>=d)return ;//剪枝 

	dis[x]=d;

	if(!col[x])col[x]=c;//最后一次的颜色 

	if(!d)return ;

	for(int i=head[x];i;i=e[i].nxt)

	{

		int y=e[i].to;

		dfs(y,d-1,c);

	}

}



int main()

{

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

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

	{

		int x,y;

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

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

	}

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

	scanf("%d",&q);

	for(int i=1;i<=q;i++)scanf("%d%d%d",&opt[i].p,&opt[i].d,&opt[i].c);

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

		dfs(opt[i].p,opt[i].d,opt[i].c);

	for(int i=1;i<=n;i++)cout<<col[i]<<"\n";

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

#include <vector>



const int MAXN = 1e5 + 100;



int n, m, Q;

int x[MAXN], d[MAXN], c[MAXN];



std::vector<int> edge[MAXN << 1];



int col[MAXN][20];



void Dfs(int x, int d, int c) {

	if (d == -1 || col[x][d])

		return;

	col[x][d] = c;

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

		int y = edge[x][i];

		Dfs(y, d - 1, c);

	}

}



int main() {

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

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

		int u, v;

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

		edge[u].push_back(v), edge[v].push_back(u);

	}

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

		edge[i].push_back(i);



	scanf("%d", &Q);

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

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



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

		Dfs(x[i], d[i], c[i]);

	

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

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

	return 0;

}

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

using namespace std;

const int maxn=101000;



struct edge{

	int to,nxt;

}e[maxn<<1];

int head[maxn],tot,n,m,q,dis[maxn],col[maxn];

void add(int x,int y)

{

	e[++tot].to=y;

	e[tot].nxt=head[x];

	head[x]=tot;

}



struct opte{

	int p,d,c;

}opt[maxn];



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

{

	if(dis[x]>=d)return ;//剪枝 

	dis[x]=d;

	if(!col[x])col[x]=c;//最后一次的颜色 

	if(!d)return ;

	for(int i=head[x];i;i=e[i].nxt)

	{

		int y=e[i].to;

		dfs(y,d-1,c);

	}

}



int main()

{

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

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

	{

		int x,y;

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

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

	}

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

	scanf("%d",&q);

	for(int i=1;i<=q;i++)scanf("%d%d%d",&opt[i].p,&opt[i].d,&opt[i].c);

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

		dfs(opt[i].p,opt[i].d,opt[i].c);

	for(int i=1;i<=n;i++)cout<<col[i]<<"\n";

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



typedef long long ll;



const int maxn = 1e5+10;



int cor[maxn][14], qwq[maxn], qaq[maxn], c[maxn];



std::vector <int> pb[maxn];



int n, m, a, b, q;



void paint(int v1, int d1, int c1)

{

    if(d1==-1)  return;

    if(cor[v1][d1] ) return;

    cor[v1][d1] = c1;

    for(int i =0;i<pb[v1].size();i++)

        paint(pb[v1][i], d1-1, c1);

}



int read()

{

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

	while(!isdigit(ch)){ if(ch == '-')f = -1, ch = getchar();}

	while(isdigit(ch)) x = x *10 + ch-'0', ch = getchar();

	return x * f;

} 



int main()

{

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

    for(int i=1;i<=m;i++) a=read(), b=read(), pb[a].push_back(b), pb[b].push_back(a);

    for(int i=1;i<=n;i++) pb[i].push_back(i);

    q=read();

    for(int i=1;i<=q;i++) qwq[i]=read(), qaq[i] = read(), c[i] = read();

    for(int i=q;i>=1;i--)  paint(qwq[i], qaq[i], c[i]);

    for(int i=1;i<=n;i++) std::cout<<cor[i][0]<<std::endl;

    return 0;

}

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

using namespace std;

const int maxn=101000;



struct edge{

	int to,nxt;

}e[maxn<<1];

int head[maxn],tot,n,m,q,dis[maxn],col[maxn];

void add(int x,int y)

{

	e[++tot].to=y;

	e[tot].nxt=head[x];

	head[x]=tot;

}



struct opte{

	int p,d,c;

}opt[maxn];



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

{

	if(dis[x]>=d)return ;//剪枝 

	dis[x]=d;

	if(!col[x])col[x]=c;//最后一次的颜色 

	if(!d)return ;

	for(int i=head[x];i;i=e[i].nxt)

	{

		int y=e[i].to;

		dfs(y,d-1,c);

	}

}



int main()

{

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

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

	{

		int x,y;

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

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

	}

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

	scanf("%d",&q);

	for(int i=1;i<=q;i++)scanf("%d%d%d",&opt[i].p,&opt[i].d,&opt[i].c);

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

		dfs(opt[i].p,opt[i].d,opt[i].c);

	for(int i=1;i<=n;i++)cout<<col[i]<<"\n";

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

#include <cctype>

#include <algorithm>

#include <cstdio>

using namespace std;

inline int read(int f = 1, int x = 0, char ch = ' ')

{

    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;

    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();

    return f*x;

}

const int N = 1e5+5;

struct Edge

{

    int next, to;

    Edge(int next = 0, int to = 0):next(next), to(to) {};

}edge[N<<1];

int tot, head[N];

void _add(int x, int y) { edge[++tot] = Edge(head[x], y), head[x] = tot; }

void add(int x, int y) { _add(x, y), _add(y, x); }

int n, m, q, col[N], u[N], d[N], w[N], f[N];

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

{

    if(f[x]>>d&1) return;

    f[x] |= ((1<<(d+1))-1), col[x] = col[x]?col[x]:c;

    for(int i = head[x]; i&&d; i = edge[i].next)

    {

        int y = edge[i].to;

        dfs(y, d-1, c);

    }

}

int main()

{

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

    for(int i = 1, x, y; i <= m; ++i) x = read(), y = read(), add(x, y);

    q = read();

    for(int i = 1; i <= q; ++i) u[i] = read(), d[i] = read(), w[i] = read();

    for(int i = q; i; --i) dfs(u[i], d[i], w[i]);

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

    return 0;

}

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

using namespace std;

const int maxn=101000;



struct edge{

	int to,nxt;

}e[maxn<<1];

int head[maxn],tot,n,m,q,dis[maxn],col[maxn];

void add(int x,int y)

{

	e[++tot].to=y;

	e[tot].nxt=head[x];

	head[x]=tot;

}



struct opte{

	int p,d,c;

}opt[maxn];



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

{

	if(dis[x]>=d)return ;//剪枝 

	dis[x]=d;

	if(!col[x])col[x]=c;//最后一次的颜色 

	if(!d)return ;

	for(int i=head[x];i;i=e[i].nxt)

	{

		int y=e[i].to;

		dfs(y,d-1,c);

	}

}



int main()

{

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

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

	{

		int x,y;

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

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

	}

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

	scanf("%d",&q);

	for(int i=1;i<=q;i++)scanf("%d%d%d",&opt[i].p,&opt[i].d,&opt[i].c);

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

		dfs(opt[i].p,opt[i].d,opt[i].c);

	for(int i=1;i<=n;i++)cout<<col[i]<<"\n";

}
// Slower C++ solution:
//

//  main.cpp

//  backToProblemSolving

//

//  Created by Khaled Abdelfattah on 6/27/17.

//  Copyright © 2017 Khaled Abdelfattah. All rights reserved.

//



#include <bits/stdc++.h>

// #include <iostream>

using namespace std;

//#include "stdc++.h"



typedef long long ll;

#define MAX 1000000000

#define BASE1 23

#define BASE2 31

#define MOD1 1000000007

#define MOD2 217645177

#define eps 1e-6



int colors[100005];

vector<int> adjList[100005];

bool visited[100005][15];

void DFS (int node, int d, int c) {

    if (d < 0 || visited[node][d])

        return;

    visited[node][d] = true;

    if (colors[node] == 0)

        colors[node] = c;

    for (int i : adjList[node])

        DFS(i, d - 1, c);

}

int main() {

    int n, m;

    cin >> n >> m;

    memset(colors, 0, n);

    memset(visited, 0, sizeof visited);

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

        int u, v;

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

        v--, u--;

        adjList[u].push_back(v);

        adjList[v].push_back(u);

    }

    int q;

    cin >> q;

    pair<pair<int, int>, int> *quers = new pair<pair<int, int>, int> [q];

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

        int s, d, c;

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

        quers[i] = {{s - 1, d}, c};

    }

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

        DFS(quers[i].first.first, quers[i].first.second, quers[i].second);

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

        cout << colors[i] << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.3437601773106174x):
#include <iostream>

#include <cstring>

#include <vector>



#define ll long long

using namespace std;

#define pb push_back

const int N = 1e5 + 5;



inline int read() {

    int x = 0; char ch = getchar();

    for (; !isdigit(ch); ch = getchar());

    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';

    return x;

}



void W(int x) { if (x >= 10) W(x / 10); putchar(x % 10 + '0'); }



vector<int> g[N];

int mx[N], n, col[N], Q, d[N], c[N], m, p[N];



void dfs(int x) {

    if (!col[x]) col[x] = c[Q];

    for (int i : g[x]) if (mx[x] - 1 > mx[i]) mx[i] = mx[x] - 1, dfs(i);

}



int main() {

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



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

    for (int i = 1, uu, vv; i <= m; i++)

        uu = read(), vv = read(), g[uu].pb(vv), g[vv].pb(uu);

    Q = read();

    for (int i = 1; i <= Q; i++) p[i] = read(), d[i] = read(), c[i] = read();



    for (; Q; Q--) if (d[Q] > mx[p[Q]]) mx[p[Q]] = d[Q], dfs(p[Q]);



    for (int i = 1; i <= n; i++) W(col[i]), puts("");

    return 0;

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

using namespace std;



const int N = 1e5 + 10;



vector <int> G[N];

int rec[N], color[N], ver[N], d[N], c[N];



void dfs(int x, int dist, int col){

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

	if (~rec[x] && dist <= rec[x]) return;

	rec[x] = dist;

	if (dist == 0) return;

	for (int i = 0; i < G[x].size(); i++) dfs(G[x][i], dist - 1, col);

}



int main(){

	int n, m, q, u, v;

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

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

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

		G[u].push_back(v);

		G[v].push_back(u);

	}

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

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

	scanf("%d",&q);

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

	for (int i = q; i >= 1; i--) dfs(ver[i], d[i], c[i]);

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1153421328706603x):
#include <iostream>

#include <cstring>

#include <vector>



#define ll long long

using namespace std;

#define pb push_back

const int N = 1e5 + 5;



inline int read() {

    int x = 0; char ch = getchar();

    for (; !isdigit(ch); ch = getchar());

    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';

    return x;

}



void W(int x) { if (x >= 10) W(x / 10); putchar(x % 10 + '0'); }



vector<int> g[N];

int mx[N], n, col[N], Q, d[N], c[N], m, p[N];



void dfs(int x) {

    if (!col[x]) col[x] = c[Q];

    for (int i : g[x]) if (mx[x] - 1 > mx[i]) mx[i] = mx[x] - 1, dfs(i);

}



int main() {

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



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

    for (int i = 1, uu, vv; i <= m; i++)

        uu = read(), vv = read(), g[uu].pb(vv), g[vv].pb(uu);

    Q = read();

    for (int i = 1; i <= Q; i++) p[i] = read(), d[i] = read(), c[i] = read();



    for (; Q; Q--) if (d[Q] > mx[p[Q]]) mx[p[Q]] = d[Q], dfs(p[Q]);



    for (int i = 1; i <= n; i++) W(col[i]), puts("");

    return 0;

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

#include <vector>



const int MAXN = 1e5 + 100;



int n, m, Q;

int x[MAXN], d[MAXN], c[MAXN];



std::vector<int> edge[MAXN << 1];



int col[MAXN][20];



void Dfs(int x, int d, int c) {

	if (d == -1 || col[x][d])

		return;

	col[x][d] = c;

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

		int y = edge[x][i];

		Dfs(y, d - 1, c);

	}

}



int main() {

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

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

		int u, v;

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

		edge[u].push_back(v), edge[v].push_back(u);

	}

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

		edge[i].push_back(i);



	scanf("%d", &Q);

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

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



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

		Dfs(x[i], d[i], c[i]);

	

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

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6302333452527904x):
#include <iostream>

#include <cstring>

#include <vector>



#define ll long long

using namespace std;

#define pb push_back

const int N = 1e5 + 5;



inline int read() {

    int x = 0; char ch = getchar();

    for (; !isdigit(ch); ch = getchar());

    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';

    return x;

}



void W(int x) { if (x >= 10) W(x / 10); putchar(x % 10 + '0'); }



vector<int> g[N];

int mx[N], n, col[N], Q, d[N], c[N], m, p[N];



void dfs(int x) {

    if (!col[x]) col[x] = c[Q];

    for (int i : g[x]) if (mx[x] - 1 > mx[i]) mx[i] = mx[x] - 1, dfs(i);

}



int main() {

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



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

    for (int i = 1, uu, vv; i <= m; i++)

        uu = read(), vv = read(), g[uu].pb(vv), g[vv].pb(uu);

    Q = read();

    for (int i = 1; i <= Q; i++) p[i] = read(), d[i] = read(), c[i] = read();



    for (; Q; Q--) if (d[Q] > mx[p[Q]]) mx[p[Q]] = d[Q], dfs(p[Q]);



    for (int i = 1; i <= n; i++) W(col[i]), puts("");

    return 0;

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

#define F(i,a,b) for(int i=(a);i<=(b);++i)

#define F2(i,a,b) for(int i=(a);i<(b);++i)

#define dF(i,a,b) for(int i=(a);i>=(b);--i)

#define dF2(i,a,b) for(int i=(a);i>(b);--i)

#define dF3(i,a,b) for(int i=(a)-1;i>=(b);--i)

using namespace std;typedef long long ll;typedef double ld;int INF=0x3f3f3f3f;int INF2=0x7fffffff;ll LNF=0x3f3f3f3f3f3f3f3f;ll LNF2=0x7fffffffffffffff;



int n,m,q;



int h[100001],D[100001],nxt[300001],to[300001],w1[300001],w2[300001],tot;

void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=tot;}

void ins2(int x,int y,int c,int i){nxt[++tot]=D[x];to[tot]=y;w1[tot]=c;w2[tot]=i;D[x]=tot;}



int C[100001],T[100001];

int C2[100001],T2[100001];



int main(){ int x,y;

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

	F(i,1,m) scanf("%d%d",&x,&y), ins(x,y), ins(y,x);

	scanf("%d",&q);

	F(i,1,q){

		int v,d,c;

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

		ins2(d,v,c,i);

	}

	dF(k,10,0){

		F(i,1,n) C2[i]=T2[i]=0;

		F(i,1,n){

			if(C[i]){

				for(int j=h[i];j;j=nxt[j]){

					if(T2[to[j]]<T[i])

						T2[to[j]]=T[i], C2[to[j]]=C[i];

				}

				if(T2[i]<T[i])

					T2[i]=T[i], C2[i]=C[i];

			}

		}

		F(i,1,n) C[i]=C2[i],T[i]=T2[i];

		for(int i=D[k];i;i=nxt[i]){

			int u=to[i], c=w1[i], t=w2[i];

			if(T[u]<t) C[u]=c, T[u]=t;

		}

	}

	F(i,1,n) printf("%d\n",C[i]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.981346393876421x):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e6+5;

typedef long long ll;

struct node{

    int u,v,nxt;

}edge[N*2];

int head[N],mcnt;

void add_edge(int u,int v){

    mcnt++;

    edge[mcnt].u=u;

    edge[mcnt].v=v;

    edge[mcnt].nxt=head[u];

    head[u]=mcnt;

}

int c[N];

int vis[N],tot;

int n,m;

int deep[N];

int q[N],h,t;

int x[N],y[N],z[N];

int maxdeep[N];

void bfs(int s,int depth,int color){

    if(depth<=maxdeep[s])

        return ;

    vis[s]=tot;

    deep[s]=depth;

    maxdeep[s]=depth;

    h=t=1;

    q[1]=s;

    while(h<=t){

        int u=q[h++];

        if(!c[u])

            c[u]=color;

        if(deep[u]==0)

            continue ;

        for(int i=head[u];i;i=edge[i].nxt){

            int v=edge[i].v;

            if(vis[v]>tot&&maxdeep[v]<deep[u]-1){

                vis[v]=tot;

                deep[v]=deep[u]-1;

                maxdeep[v]=deep[u]-1;

                q[++t]=v;

            }

        }

    }

}

int main()

{

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

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

        int u,v;

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

        add_edge(u,v);

        add_edge(v,u);

    }

    int qu;

    scanf("%d",&qu);

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

        scanf("%d%d%d",&x[i],&y[i],&z[i]);

    }

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

        vis[i]=qu+1,maxdeep[i]=-1;

    for(tot=qu;tot>=1;tot--){

        bfs(x[tot],y[tot],z[tot]);

    }

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

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

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

using namespace std;

typedef vector<int> vi;

const int maxn=100005,INF=0x3f3f3f3f,mod=1000000007;

struct QES{

	int v,d,c;

	QES(){}

	QES(int x,int y,int z){v=x;d=y;c=z;}

}qes[maxn];

int n,m,q,vis[maxn],col[maxn];

vi eg[maxn];

void dfs(QES nd){

	if(col[nd.v]==0) col[nd.v]=nd.c;

	if(nd.d==0) return;

	for(int i=0;i<eg[nd.v].size();i++){

		if(vis[eg[nd.v][i]]<nd.d-1){

			vis[eg[nd.v][i]]=nd.d-1;

			dfs(QES(eg[nd.v][i],nd.d-1,nd.c));

		}

	}

}

int main(){

	int t1,t2;

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

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

		scanf("%d%d",&t1,&t2);

		eg[t1].push_back(t2);

		eg[t2].push_back(t1);

	}

	scanf("%d",&q);

	for(int i=0;i<q;i++) scanf("%d%d%d",&qes[i].v,&qes[i].d,&qes[i].c);

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

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

		if(vis[qes[i].v]<qes[i].d){

			vis[qes[i].v]=qes[i].d;

			dfs(qes[i]);

		}

	}

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1077968595510752x):
/***********************

*  Date: 2018.11.28    *

*  Problem:            *

*  Author: xuziyuan    * 

***********************/



#include <bits/stdc++.h>



#define rt0 return 0

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

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

#define replet(c) for(char c='a';c<='z';c++)

#define LL long long

#define pii pair <int,int>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

#define sqr(a) ((a)*(a))



using namespace std;



const LL MOD=1e9+7;



int n,m,q,appe[100010][20],coap[100010];//appe:appearance

vector <int> g[100010];



int main()

{

	cin>>n>>m;

	rep(i,m)

	{

		int x,y;

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

		g[x].pb(y);

		g[y].pb(x);

	}

	cin>>q;

	repn(i,q)

	{

		int x,y;

		scanf("%d%d%d",&x,&y,&coap[i]);

		appe[x][y]=i;

	}

	for(int i=9;i>=0;i--)//算能不能覆盖appe[j][i]之前要先算出appe[p][i+1]会不会被覆盖，所以i要倒着循环 

	{

		repn(p,n)

		{

			rep(k,g[p].size())//i在这里代表可以控制的范围

			{

				int j=g[p][k];

				appe[j][i]=max(appe[j][i],appe[p][i+1]);/*远一条边距离就要加1，这里是看后者可不可以覆盖前者，

				可以说是一种dp，一个类似递归的过程，如果再之前的点把后者覆盖了，也会在前者上体现出来*/

			}	

		}	

	} 

	repn(i,n)

	{

		int lst=0;

		rep(j,11) lst=max(lst,appe[i][j]);

		cout<<coap[lst]<<endl;

	}

	rt0;

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

using namespace std;

typedef vector<int> vi;

const int maxn=100005,INF=0x3f3f3f3f,mod=1000000007;

struct QES{

	int v,d,c;

	QES(){}

	QES(int x,int y,int z){v=x;d=y;c=z;}

}qes[maxn];

int n,m,q,vis[maxn],col[maxn];

vi eg[maxn];

void dfs(QES nd){

	if(col[nd.v]==0) col[nd.v]=nd.c;

	if(nd.d==0) return;

	for(int i=0;i<eg[nd.v].size();i++){

		if(vis[eg[nd.v][i]]<nd.d-1){

			vis[eg[nd.v][i]]=nd.d-1;

			dfs(QES(eg[nd.v][i],nd.d-1,nd.c));

		}

	}

}

int main(){

	int t1,t2;

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

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

		scanf("%d%d",&t1,&t2);

		eg[t1].push_back(t2);

		eg[t2].push_back(t1);

	}

	scanf("%d",&q);

	for(int i=0;i<q;i++) scanf("%d%d%d",&qes[i].v,&qes[i].d,&qes[i].c);

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

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

		if(vis[qes[i].v]<qes[i].d){

			vis[qes[i].v]=qes[i].d;

			dfs(qes[i]);

		}

	}

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.9769401451072826x):
//#pragma GCC optimize(2)

//#pragma GCC optimize(3)

#include <bits/stdc++.h>

#define N 100005

#define int long long

//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1 == p2)?EOF:*p1++)

using namespace std ;

//char buf[(1 << 22)] , *p1 = buf , *p2 = buf ;

inline int read ()

{

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

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

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

    return x * f ;

}

int n , m , ver[N << 1] , nxt[N << 1] , hed[N] , tot , ans[N] , Dis[N] ;

struct as {

	int v , d , c ;

} a[N] ;

void add (int x , int y) { ver[++ tot] = y ; nxt[tot] = hed[x] ; hed[x] = tot ; }

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

{

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

	if (! dis || Dis[x] >= dis) return ;

	Dis[x] = dis ;

	for (int i = hed[x] ; i ; i = nxt[i])

	{

		int y = ver[i] ;

		dfs (y , col , dis - 1) ;

	}

}

signed main ()

{

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

	for (int i = 1 , u , v ; i <= m ; u = read () , v = read () , add (u , v) , add (v , u) , i ++) ;

	int q = read () ;

	for (int i = 1 ; i <= q ; i ++) a[i].v = read () , a[i].d = read () , a[i].c = read () ;

	for (int i = q ; i >= 1 ; i --) dfs (a[i].v , a[i].c , a[i].d) ;

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

}

/*

7 7

1 2

1 3

1 4

4 5	

5 6

5 7

2 3

2

6 1 1

1 2 2

*/