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

using namespace std;

int n,m;

int q;

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

vector<int> g[100005];

int colour[100005];

int mindis[100005];

inline void dfs(int x,int dleft,int c)

{

	if(dleft<=mindis[x])

	{

		return;

	}

	mindis[x]=dleft;

	if(colour[x]==0)

	{

		colour[x]=c;

	}

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

	{

		dfs(g[x][i],dleft-1,c);

	}

}

int main()

{

	cin>>n>>m;

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

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

	{

		int a,b;

		cin>>a>>b;

		a--;

		b--;

		g[a].push_back(b);

		g[b].push_back(a);

	}

	cin>>q;

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

	{

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

	}

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

	{

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

	}

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

	{

		cout<<colour[i]<<endl;

	}

	return 0;

}

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

#include<cstdio>



const int SIZE = 100000 + 7;



using namespace std;



struct query{

	int d, v, c;

}que[SIZE];



int f[SIZE][14];

int head[SIZE], ver[SIZE * 2], nxt[SIZE * 2];

int N, M, Q, tot = 1;



inline void add(const int &u, const int &v) {

	ver[++tot] = v;

	nxt[tot] = head[u];

	head[u] = tot;

}



inline void BFS(const int &s, const int &d, const int &c) {

	f[s][d] = c;

	if( !d ) return;

	

	if(!f[s][d - 1]) BFS(s, d - 1, c);

	for(int i = head[s]; i; i = nxt[i]) {

		int v = ver[i];

		if(!f[v][d - 1]) BFS(v, d - 1, c);

	}

}



int main() {

	scanf("%d%d",&N,&M);

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

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

		add(a, b); add(b, a);

	}

	scanf("%d",&Q);

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

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

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

		if(!f[que[i].v][que[i].d]) BFS(que[i].v, que[i].d, que[i].c);

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

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

	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: 4.371315382912182x):
#include<iostream>

#include<cstdio>



const int SIZE = 100000 + 7;



using namespace std;



struct query{

	int d, v, c;

}que[SIZE];



int f[SIZE][14];

int head[SIZE], ver[SIZE * 2], nxt[SIZE * 2];

int N, M, Q, tot = 1;



inline void add(const int &u, const int &v) {

	ver[++tot] = v;

	nxt[tot] = head[u];

	head[u] = tot;

}



inline void BFS(const int &s, const int &d, const int &c) {

	f[s][d] = c;

	if( !d ) return;

	

	if(!f[s][d - 1]) BFS(s, d - 1, c);

	for(int i = head[s]; i; i = nxt[i]) {

		int v = ver[i];

		if(!f[v][d - 1]) BFS(v, d - 1, c);

	}

}



int main() {

	scanf("%d%d",&N,&M);

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

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

		add(a, b); add(b, a);

	}

	scanf("%d",&Q);

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

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

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

		if(!f[que[i].v][que[i].d]) BFS(que[i].v, que[i].d, que[i].c);

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

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

	return 0;

}
// 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: 3.758959950563773x):
#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;



int head[100005], tot, n, m, q, v[100005], d[100005], c[100005], ou[100005], maxd[100005];

struct edge {

	int to, nxt;

} G[300005];



inline void add(int u, int v) {

	tot++;

	G[tot].to = v;

	G[tot].nxt = head[u];

	head[u] = tot;

}



void dfs(int un, int ds, int c) {

	if(maxd[un] >= ds) return;

	if(!ou[un]) ou[un] = c;

	if(!ds) return;

	maxd[un] = ds;

	for (int i = head[un]; i; i = G[i].nxt) dfs(G[i].to, ds - 1, c);

}



int main() {

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

	int u, vd;

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

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

		add(u, vd); add(vd, u);

	}

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

	scanf ("%d", &q);

	for (int i = 1; i <= q; i++) scanf ("%d %d %d", &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++) printf ("%d\n", ou[i]);

	return 0;

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

using namespace std;

int n,m;

int q;

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

vector<int> g[100005];

int colour[100005];

int mindis[100005];

inline void dfs(int x,int dleft,int c)

{

	if(dleft<=mindis[x])

	{

		return;

	}

	mindis[x]=dleft;

	if(colour[x]==0)

	{

		colour[x]=c;

	}

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

	{

		dfs(g[x][i],dleft-1,c);

	}

}

int main()

{

	cin>>n>>m;

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

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

	{

		int a,b;

		cin>>a>>b;

		a--;

		b--;

		g[a].push_back(b);

		g[b].push_back(a);

	}

	cin>>q;

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

	{

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

	}

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

	{

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

	}

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

	{

		cout<<colour[i]<<endl;

	}

	return 0;

}

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

#include <cstring>

#include <cstdio>

using namespace std;



int head[100005], tot, n, m, q, v[100005], d[100005], c[100005], ou[100005], maxd[100005];

struct edge {

	int to, nxt;

} G[300005];



inline void add(int u, int v) {

	tot++;

	G[tot].to = v;

	G[tot].nxt = head[u];

	head[u] = tot;

}



void dfs(int un, int ds, int c) {

	if(maxd[un] >= ds) return;

	if(!ou[un]) ou[un] = c;

	if(!ds) return;

	maxd[un] = ds;

	for (int i = head[un]; i; i = G[i].nxt) dfs(G[i].to, ds - 1, c);

}



int main() {

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

	int u, vd;

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

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

		add(u, vd); add(vd, u);

	}

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

	scanf ("%d", &q);

	for (int i = 1; i <= q; i++) scanf ("%d %d %d", &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++) printf ("%d\n", ou[i]);

	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: 3.1199960226742642x):
#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;



int head[100005], tot, n, m, q, v[100005], d[100005], c[100005], ou[100005], maxd[100005];

struct edge {

	int to, nxt;

} G[300005];



inline void add(int u, int v) {

	tot++;

	G[tot].to = v;

	G[tot].nxt = head[u];

	head[u] = tot;

}



void dfs(int un, int ds, int c) {

	if(maxd[un] >= ds) return;

	if(!ou[un]) ou[un] = c;

	if(!ds) return;

	maxd[un] = ds;

	for (int i = head[un]; i; i = G[i].nxt) dfs(G[i].to, ds - 1, c);

}



int main() {

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

	int u, vd;

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

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

		add(u, vd); add(vd, u);

	}

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

	scanf ("%d", &q);

	for (int i = 1; i <= q; i++) scanf ("%d %d %d", &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++) printf ("%d\n", ou[i]);

	return 0;

}
// 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: 5.331227343127729x):
#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

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

using namespace std;

int n,m;

int q;

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

vector<int> g[100005];

int colour[100005];

int mindis[100005];

inline void dfs(int x,int dleft,int c)

{

	if(dleft<=mindis[x])

	{

		return;

	}

	mindis[x]=dleft;

	if(colour[x]==0)

	{

		colour[x]=c;

	}

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

	{

		dfs(g[x][i],dleft-1,c);

	}

}

int main()

{

	cin>>n>>m;

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

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

	{

		int a,b;

		cin>>a>>b;

		a--;

		b--;

		g[a].push_back(b);

		g[b].push_back(a);

	}

	cin>>q;

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

	{

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

	}

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

	{

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

	}

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

	{

		cout<<colour[i]<<endl;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.9961269799291044x):
#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

*/
// 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: 4.425002746846532x):
#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

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

#include <cstring>

#include <cstdio>

using namespace std;



int head[100005], tot, n, m, q, v[100005], d[100005], c[100005], ou[100005], maxd[100005];

struct edge {

	int to, nxt;

} G[300005];



inline void add(int u, int v) {

	tot++;

	G[tot].to = v;

	G[tot].nxt = head[u];

	head[u] = tot;

}



void dfs(int un, int ds, int c) {

	if(maxd[un] >= ds) return;

	if(!ou[un]) ou[un] = c;

	if(!ds) return;

	maxd[un] = ds;

	for (int i = head[un]; i; i = G[i].nxt) dfs(G[i].to, ds - 1, c);

}



int main() {

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

	int u, vd;

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

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

		add(u, vd); add(vd, u);

	}

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

	scanf ("%d", &q);

	for (int i = 1; i <= q; i++) scanf ("%d %d %d", &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++) printf ("%d\n", ou[i]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.418271919158954x):
#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

*/
// 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: 6.467779543284722x):
#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

*/