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

using namespace std;



#define iii pair<pair<int,int>,int> 

#define FIR first.first

#define SEC first.second

#define THI second



int N,M;

vector<int> e[100010];

int Q;

iii q[100010];



int g[100010];

int maxd[100010];



void input()

{

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

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

	{

		maxd[i]=-1;

	}

	for(int i=1,tmp1,tmp2;i<=M;i++)

	{

		scanf("%d%d",&tmp1,&tmp2);

		e[tmp1].push_back(tmp2);

		e[tmp2].push_back(tmp1);

	}

	scanf("%d",&Q);

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

	{

		scanf("%d%d%d",&q[i].FIR,&q[i].SEC,&q[i].THI);

	}

}



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

{

	if(d<=maxd[v])

	{

		return;

	}

	maxd[v]=d;

	

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

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

	{

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

	}

}



void work()

{

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

	{

		f(q[i].FIR,q[i].SEC,q[i].THI);

	}

}



void output()

{

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

	{

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

	}

}



int main()

{

	input();

	work();

	output();

	return 0;

}


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



using namespace std;

typedef long long ll;



struct jie

{

    int x,t,c;

}mp[500005];

struct jie1

{

    int v,d,c;

}a[500005];

int d[500005],us[500005],head[500005],cnt,n,c[500005],f[500005][12];

void add(int x,int y,int c)

{

    cnt++;

    mp[cnt].x=y;

    mp[cnt].c=c;

    mp[cnt].t=head[x];

    head[x]=cnt;

}

void dfs(int u,int d,int l,int co)

{

    if(d>l||f[u][l-d]==1) return ;

    for(int j=0;j<=l-d;j++)

    {

        f[u][j]=1;

    }

    if(c[u]==0)

    {

        c[u]=co;

    }

    int i;

    for(i=head[u];i!=-1;i=mp[i].t)

    {

        int v=mp[i].x;

        dfs(v,d+1,l,co);

    }

    return ;

}

int main()

{

    int m,i;

    cnt=1;

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

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

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

    {

        int u,v;

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

        add(u,v,1);

        add(v,u,1);

    }

    int T;

    scanf("%d",&T);

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

    {

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

    }

    for(i=T;i>=1;i--)

    {

        dfs(a[i].v,0,a[i].d,a[i].c);

    }

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

    {

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

    }

    return 0;

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

using namespace std;



#define iii pair<pair<int,int>,int> 

#define FIR first.first

#define SEC first.second

#define THI second



int N,M;

vector<int> e[100010];

int Q;

iii q[100010];



int g[100010];

int maxd[100010];



void input()

{

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

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

	{

		maxd[i]=-1;

	}

	for(int i=1,tmp1,tmp2;i<=M;i++)

	{

		scanf("%d%d",&tmp1,&tmp2);

		e[tmp1].push_back(tmp2);

		e[tmp2].push_back(tmp1);

	}

	scanf("%d",&Q);

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

	{

		scanf("%d%d%d",&q[i].FIR,&q[i].SEC,&q[i].THI);

	}

}



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

{

	if(d<=maxd[v])

	{

		return;

	}

	maxd[v]=d;

	

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

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

	{

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

	}

}



void work()

{

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

	{

		f(q[i].FIR,q[i].SEC,q[i].THI);

	}

}



void output()

{

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

	{

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

	}

}



int main()

{

	input();

	work();

	output();

	return 0;

}


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



using namespace std;

typedef long long ll;



struct jie

{

    int x,t,c;

}mp[500005];

struct jie1

{

    int v,d,c;

}a[500005];

int d[500005],us[500005],head[500005],cnt,n,c[500005],f[500005][12];

void add(int x,int y,int c)

{

    cnt++;

    mp[cnt].x=y;

    mp[cnt].c=c;

    mp[cnt].t=head[x];

    head[x]=cnt;

}

void dfs(int u,int d,int l,int co)

{

    if(d>l||f[u][l-d]==1) return ;

    for(int j=0;j<=l-d;j++)

    {

        f[u][j]=1;

    }

    if(c[u]==0)

    {

        c[u]=co;

    }

    int i;

    for(i=head[u];i!=-1;i=mp[i].t)

    {

        int v=mp[i].x;

        dfs(v,d+1,l,co);

    }

    return ;

}

int main()

{

    int m,i;

    cnt=1;

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

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

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

    {

        int u,v;

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

        add(u,v,1);

        add(v,u,1);

    }

    int T;

    scanf("%d",&T);

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

    {

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

    }

    for(i=T;i>=1;i--)

    {

        dfs(a[i].v,0,a[i].d,a[i].c);

    }

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

    {

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

    }

    return 0;

}


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

using namespace std;



#define iii pair<pair<int,int>,int> 

#define FIR first.first

#define SEC first.second

#define THI second



int N,M;

vector<int> e[100010];

int Q;

iii q[100010];



int g[100010];

int maxd[100010];



void input()

{

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

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

	{

		maxd[i]=-1;

	}

	for(int i=1,tmp1,tmp2;i<=M;i++)

	{

		scanf("%d%d",&tmp1,&tmp2);

		e[tmp1].push_back(tmp2);

		e[tmp2].push_back(tmp1);

	}

	scanf("%d",&Q);

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

	{

		scanf("%d%d%d",&q[i].FIR,&q[i].SEC,&q[i].THI);

	}

}



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

{

	if(d<=maxd[v])

	{

		return;

	}

	maxd[v]=d;

	

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

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

	{

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

	}

}



void work()

{

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

	{

		f(q[i].FIR,q[i].SEC,q[i].THI);

	}

}



void output()

{

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

	{

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

	}

}



int main()

{

	input();

	work();

	output();

	return 0;

}


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

using namespace std;

const int N = 1e5+20;

struct edge { int ver,next; } e[N<<1];

int n,m,q,t,Head[N],ans[N],v[N],d[N],c[N],dis[N];

inline void insert(int x,int y) { e[++t] = (edge){y,Head[x]} , Head[x] = t; }

inline void input(void)

{

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

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

    {

        int u,v;

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

        insert( u , v );

        insert( v , u );

    }

    scanf("%d",&q);

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

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

}

inline void dfs(int x,int d,int col)

{

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

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

    dis[x] = d;

    for (int i=Head[x];i;i=e[i].next)

    {

        int y = e[i].ver;

        dfs( y , d-1 , col );

    }

}

int main(void)

{

    input();

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

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

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

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

    return 0;

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



using namespace std;

typedef long long ll;



struct jie

{

    int x,t,c;

}mp[500005];

struct jie1

{

    int v,d,c;

}a[500005];

int d[500005],us[500005],head[500005],cnt,n,c[500005],f[500005][12];

void add(int x,int y,int c)

{

    cnt++;

    mp[cnt].x=y;

    mp[cnt].c=c;

    mp[cnt].t=head[x];

    head[x]=cnt;

}

void dfs(int u,int d,int l,int co)

{

    if(d>l||f[u][l-d]==1) return ;

    for(int j=0;j<=l-d;j++)

    {

        f[u][j]=1;

    }

    if(c[u]==0)

    {

        c[u]=co;

    }

    int i;

    for(i=head[u];i!=-1;i=mp[i].t)

    {

        int v=mp[i].x;

        dfs(v,d+1,l,co);

    }

    return ;

}

int main()

{

    int m,i;

    cnt=1;

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

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

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

    {

        int u,v;

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

        add(u,v,1);

        add(v,u,1);

    }

    int T;

    scanf("%d",&T);

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

    {

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

    }

    for(i=T;i>=1;i--)

    {

        dfs(a[i].v,0,a[i].d,a[i].c);

    }

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

    {

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

    }

    return 0;

}


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

using namespace std;

const int N = 1e5+20;

struct edge { int ver,next; } e[N<<1];

int n,m,q,t,Head[N],ans[N],v[N],d[N],c[N],dis[N];

inline void insert(int x,int y) { e[++t] = (edge){y,Head[x]} , Head[x] = t; }

inline void input(void)

{

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

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

    {

        int u,v;

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

        insert( u , v );

        insert( v , u );

    }

    scanf("%d",&q);

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

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

}

inline void dfs(int x,int d,int col)

{

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

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

    dis[x] = d;

    for (int i=Head[x];i;i=e[i].next)

    {

        int y = e[i].ver;

        dfs( y , d-1 , col );

    }

}

int main(void)

{

    input();

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

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

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

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

    return 0;

}
// Slower C++ solution:
#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";

}


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

using namespace std;

const int N = 1e5+20;

struct edge { int ver,next; } e[N<<1];

int n,m,q,t,Head[N],ans[N],v[N],d[N],c[N],dis[N];

inline void insert(int x,int y) { e[++t] = (edge){y,Head[x]} , Head[x] = t; }

inline void input(void)

{

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

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

    {

        int u,v;

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

        insert( u , v );

        insert( v , u );

    }

    scanf("%d",&q);

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

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

}

inline void dfs(int x,int d,int col)

{

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

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

    dis[x] = d;

    for (int i=Head[x];i;i=e[i].next)

    {

        int y = e[i].ver;

        dfs( y , d-1 , col );

    }

}

int main(void)

{

    input();

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

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

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

        printf("%d\n",ans[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.618451398155547x):
#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=100005,MAXM=200005;

int n,m,q;

int cl[MAXN],co[MAXN];

struct edge

{

	int v,nxt;

	edge(){}

	edge(int vv,int nn)

	{

		v=vv,nxt=nn;

	}

}E[MAXM];

int w[MAXN],ncnt=0;

void addedge(int u,int v)

{

	E[++ncnt]=edge(v,w[u]);

	w[u]=ncnt;

	E[++ncnt]=edge(u,w[v]);

	w[v]=ncnt;

}

struct node

{

	int u,t,id;

	node(){}

	node(int uu,int tt,int ii)

	{

		u=uu,t=tt,id=ii;

	}

	bool operator<(const node &a)const

	{

		if(a.t==t)

			return a.id>id;

		return a.t>t;

	}

};

struct Que

{

	int v,d,c;

}que[MAXN];

priority_queue<node>Q;

int main()

{

	//freopen("splatter.in","r",stdin);

	//freopen("splatter.out","w",stdout);

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

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

	{

		int u,v;

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

		addedge(u,v);

	}

	scanf("%d",&q);

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

	{

		int v,d,c;

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

		Q.push(node(v,d,i));

		co[i]=c;

	}

	while(!Q.empty())

	{

		node x=Q.top();

		Q.pop();

		if(cl[x.u]>=x.id)

			continue;

		cl[x.u]=x.id;

		if(x.t==0)

			continue;

		for(int i=w[x.u];i;i=E[i].nxt)

		{

			int v=E[i].v;

			if(cl[v]>=x.id)

				continue;

			Q.push(node(v,x.t-1,x.id));

		}

	}

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

	{

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

	}

	fclose(stdin);

	fclose(stdout);

}
// 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.334098583429476x):
#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;

}
// 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.2047963918049578x):
#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;

}
// 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.266545000774104x):
#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;

}