stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
/***********************

*  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,co[100010],most[100010];

vector <int> g[100010];

vector <pair<int,pii> > qs;

bool vis[100010];



int main()

{

	cin>>n>>m;

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

	rep(i,m)

	{

		int x,y;

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

		g[x].pb(y);

		g[y].pb(x);

	}

	cin>>q;

	rep(i,q)

	{

		int x,y,z;

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

		qs.pb({x,{y,z}});

	}

	for(int i=qs.size()-1;i>=0;i--)

	{

		//cout<<qs[i].fi<<' '<<qs[i].se.fi<<' '<<qs[i].se.se<<endl;

		memset(vis,0,sizeof(vis));

		int v=qs[i].fi,colo=qs[i].se.se,dist=qs[i].se.fi;

		queue <pii> q;

		q.push({v,0});

		while(!q.empty())

		{

			int pos=q.front().fi,dist1=q.front().se;

			//cout<<pos<<' '<<colo<<' '<<dist<<' '<<dist1<<endl;

			q.pop();

			if(vis[pos]) continue;

			if(most[pos]>=dist-dist1) continue;

			vis[pos]=true;

			most[pos]=dist-dist1;

			if(co[pos]==0) co[pos]=colo;

			if(dist1==dist) continue;

			rep(j,g[pos].size()) q.push({g[pos][j],dist1+1});

		}

	}

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

	rt0;

}

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

*  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],len=0;//appe:appearance

int list_top[200010],val[200010],nxt[200010];



void add(int x,int y)

{

	val[++len]=y;

	nxt[len]=list_top[x];

	list_top[x]=len;

}



int main()

{

	cin>>n>>m;

	rep(i,m)

	{

		int x,y;

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

		add(x,y);

		add(y,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)

		{

			for(int k=list_top[p];k!=0;k=nxt[k])//i在这里代表可以控制的范围

			{

				int j=val[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:
/***********************

*  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,co[100010],most[100010];

vector <int> g[100010];

vector <pair<int,pii> > qs;

bool vis[100010];



void dfs(int pos,int now,int all,int colo)

{

	if(all-now<=most[pos]) return;

	most[pos]=all-now;

	if(co[pos]==0) co[pos]=colo;

	if(now==all) return;

	rep(i,g[pos].size()) dfs(g[pos][i],now+1,all,colo);

}



int main()

{

	cin>>n>>m;

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

	rep(i,m)

	{

		int x,y;

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

		g[x].pb(y);

		g[y].pb(x);

	}

	cin>>q;

	rep(i,q)

	{

		int x,y,z;

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

		qs.pb({x,{y,z}});

	}

	reverse(qs.begin(),qs.end());

	rep(i,q)

	{

		dfs(qs[i].fi,0,qs[i].se.fi,qs[i].se.se);

	}

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

	rt0;

}

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

*  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],len=0;//appe:appearance

int list_top[200010],val[200010],nxt[200010];



void add(int x,int y)

{

	val[++len]=y;

	nxt[len]=list_top[x];

	list_top[x]=len;

}



int main()

{

	cin>>n>>m;

	rep(i,m)

	{

		int x,y;

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

		add(x,y);

		add(y,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)

		{

			for(int k=list_top[p];k!=0;k=nxt[k])//i在这里代表可以控制的范围

			{

				int j=val[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:
/***********************

*  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;

}

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

*  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],len=0;//appe:appearance

int list_top[200010],val[200010],nxt[200010];



void add(int x,int y)

{

	val[++len]=y;

	nxt[len]=list_top[x];

	list_top[x]=len;

}



int main()

{

	cin>>n>>m;

	rep(i,m)

	{

		int x,y;

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

		add(x,y);

		add(y,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)

		{

			for(int k=list_top[p];k!=0;k=nxt[k])//i在这里代表可以控制的范围

			{

				int j=val[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:
//************************

//*  Date: 2018.10.22    *

//*  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;

vector <int> g[100010];

int colo[100010],most[100010];

vector <pair<pii,int> > pa;

bool vis[100010];



int main()

{

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

	cin>>n>>m;

	rep(i,m)

	{

		int x,y;

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

		g[x].pb(y);

		g[y].pb(x);

	}

	cin>>q;

	rep(i,q)

	{

		int x,y,z;

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

		pa.pb({{x,y},z});

	}

	for(int i=pa.size()-1;i>=0;i--)

	{

		int x=pa[i].fi.fi,y=pa[i].fi.se,z=pa[i].se;

		queue <pii> q;

		q.push({x,0});

		memset(vis,0,sizeof(vis));

		while(!q.empty())

		{

			int pos=q.front().fi,all=q.front().se;

			q.pop();

			if(y-all<=most[pos]) continue;

			most[pos]=y-all;

			if(all>y) continue;

			if(vis[pos]) continue;

			//if(x==1) cout<<pos<<endl;

			vis[pos]=true;

			if(colo[pos]==0) colo[pos]=z;

			rep(i,g[pos].size()) q.push({g[pos][i],all+1});

		}

	}

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

	rt0;

}

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

*  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],len=0;//appe:appearance

int list_top[100010],val[200010],nxt[200010];



void add(int x,int y)

{

	val[++len]=y;

	nxt[len]=list_top[x];

	list_top[x]=len;

}



int main()

{

	cin>>n>>m;

	rep(i,m)

	{

		int x,y;

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

		add(x,y);

		add(y,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)

		{

			for(int k=list_top[p];k!=0;k=nxt[k])//i在这里代表可以控制的范围

			{

				int j=val[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:
/***********************

*  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,co[100010],most[100010];

vector <int> g[100010];

vector <pair<int,pii> > qs;

bool vis[100010];



int main()

{

	cin>>n>>m;

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

	rep(i,m)

	{

		int x,y;

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

		g[x].pb(y);

		g[y].pb(x);

	}

	cin>>q;

	rep(i,q)

	{

		int x,y,z;

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

		qs.pb({x,{y,z}});

	}

	for(int i=qs.size()-1;i>=0;i--)

	{

		//cout<<qs[i].fi<<' '<<qs[i].se.fi<<' '<<qs[i].se.se<<endl;

		memset(vis,0,sizeof(vis));

		int v=qs[i].fi,colo=qs[i].se.se,dist=qs[i].se.fi;

		queue <pii> q;

		q.push({v,0});

		while(!q.empty())

		{

			int pos=q.front().fi,dist1=q.front().se;

			//cout<<pos<<' '<<colo<<' '<<dist<<' '<<dist1<<endl;

			q.pop();

			if(most[pos]>=dist-dist1) continue;

			most[pos]=dist-dist1;

			if(vis[pos]) continue;

			vis[pos]=true;

			if(co[pos]==0) co[pos]=colo;

			if(dist1==dist) continue;

			rep(j,g[pos].size()) q.push({g[pos][j],dist1+1});

		}

	}

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

	rt0;

}

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

*  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],len=0;//appe:appearance

int list_top[100010],val[200010],nxt[200010];



void add(int x,int y)

{

	val[++len]=y;

	nxt[len]=list_top[x];

	list_top[x]=len;

}



int main()

{

	cin>>n>>m;

	rep(i,m)

	{

		int x,y;

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

		add(x,y);

		add(y,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)

		{

			for(int k=list_top[p];k!=0;k=nxt[k])//i在这里代表可以控制的范围

			{

				int j=val[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:
/***********************

*  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,co[100010],most[100010];

vector <int> g[100010];

vector <pair<int,pii> > qs;

bool vis[100010];



int main()

{

	cin>>n>>m;

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

	rep(i,m)

	{

		int x,y;

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

		g[x].pb(y);

		g[y].pb(x);

	}

	cin>>q;

	rep(i,q)

	{

		int x,y,z;

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

		qs.pb({x,{y,z}});

	}

	for(int i=qs.size()-1;i>=0;i--)

	{

		//cout<<qs[i].fi<<' '<<qs[i].se.fi<<' '<<qs[i].se.se<<endl;

		memset(vis,0,sizeof(vis));

		int v=qs[i].fi,colo=qs[i].se.se,dist=qs[i].se.fi;

		queue <pii> q;

		q.push({v,0});

		while(!q.empty())

		{

			int pos=q.front().fi,dist1=q.front().se;

			//cout<<pos<<' '<<colo<<' '<<dist<<' '<<dist1<<endl;

			q.pop();

			if(vis[pos]) continue;

			if(most[pos]>=dist-dist1) continue;

			vis[pos]=true;

			most[pos]=dist-dist1;

			if(co[pos]==0) co[pos]=colo;

			if(dist1==dist) continue;

			rep(j,g[pos].size()) q.push({g[pos][j],dist1+1});

		}

	}

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

	rt0;

}

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

*  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],len=0;//appe:appearance

int list_top[100010],val[200010],nxt[200010];



void add(int x,int y)

{

	val[++len]=y;

	nxt[len]=list_top[x];

	list_top[x]=len;

}



int main()

{

	cin>>n>>m;

	rep(i,m)

	{

		int x,y;

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

		add(x,y);

		add(y,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)

		{

			for(int k=list_top[p];k!=0;k=nxt[k])//i在这里代表可以控制的范围

			{

				int j=val[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:
/***********************

*  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,co[100010],most[100010];

vector <int> g[100010];

vector <pair<int,pii> > qs;

bool vis[100010];



void dfs(int pos,int now,int all,int colo)

{

	if(all-now<=most[pos]) return;

	most[pos]=all-now;

	if(co[pos]==0) co[pos]=colo;

	if(now==all) return;

	rep(i,g[pos].size()) dfs(g[pos][i],now+1,all,colo);

}



int main()

{

	cin>>n>>m;

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

	rep(i,m)

	{

		int x,y;

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

		g[x].pb(y);

		g[y].pb(x);

	}

	cin>>q;

	rep(i,q)

	{

		int x,y,z;

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

		qs.pb({x,{y,z}});

	}

	reverse(qs.begin(),qs.end());

	rep(i,q)

	{

		dfs(qs[i].fi,0,qs[i].se.fi,qs[i].se.se);

	}

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

	rt0;

}

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

*  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],len=0;//appe:appearance

int list_top[100010],val[200010],nxt[200010];



void add(int x,int y)

{

	val[++len]=y;

	nxt[len]=list_top[x];

	list_top[x]=len;

}



int main()

{

	cin>>n>>m;

	rep(i,m)

	{

		int x,y;

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

		add(x,y);

		add(y,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)

		{

			for(int k=list_top[p];k!=0;k=nxt[k])//i在这里代表可以控制的范围

			{

				int j=val[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:
/***********************

*  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;

}

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

*  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],len=0;//appe:appearance

int list_top[100010],val[200010],nxt[200010];



void add(int x,int y)

{

	val[++len]=y;

	nxt[len]=list_top[x];

	list_top[x]=len;

}



int main()

{

	cin>>n>>m;

	rep(i,m)

	{

		int x,y;

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

		add(x,y);

		add(y,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)

		{

			for(int k=list_top[p];k!=0;k=nxt[k])//i在这里代表可以控制的范围

			{

				int j=val[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;





int main() {

	int N;

	cin >> N;

	vector<int>D( N );

	for( size_t i = 0; i < N; i++ ) {

		cin >> D[i];

	}

	double maxans = 1, minans = 0;

	for( size_t idx = 0; idx < 100; idx++ ) {

		double midans = ( maxans + minans ) / 2;

		set<int>prev;

		prev.insert( 1 );

		for( size_t i = 0; i < N; i++ ) {

			double minvalue = D[i] * ( 1. - midans );

			double maxvalue = D[i] * ( 1. + midans );

			set<int>next;

			for( auto one : prev ) {

				for( int j = minvalue / one + 1; j <= maxvalue / one; j++ ) {

					next.insert( j*one );

				}

			}

			prev = next;

		}

		if( prev.size() ) {

			maxans = midans;

		} else {

			minans = midans;

		}



	}

	cout << fixed << setprecision( 20 ) << minans << endl;

}

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

/*

*/



using namespace std;





int main() {

	int N;

	cin >> N;

	vector<int>D( N );

	for( size_t i = 0; i < N; i++ ) {

		cin >> D[i];

	}

	double maxans = 1, minans = 0;

	for( size_t idx = 0; idx < 50; idx++ ) {

		double midans = ( maxans + minans ) / 2;

		set<int>prev;

		prev.insert( 1 );

		for( size_t i = 0; i < N; i++ ) {

			double minvalue = D[i] * ( 1. - midans );

			double maxvalue = D[i] * ( 1. + midans );

			set<int>next;

			for( auto one : prev ) {

				for( int j = minvalue / one + 1; j <= maxvalue / one; j++ ) {

					next.insert( j*one );

				}

			}

			prev = next;

		}

		if( prev.size() ) {

			maxans = midans;

		} else {

			minans = midans;

		}



	}

	cout << fixed << setprecision( 20 ) << minans << endl;

}