#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<char,int> >a[200010];
bool v[200010];
int ans[200010];
struct jgt
{
	int u,len;
	char c;
};
jgt mj(int u,int len,char c)
{
	jgt tmp;
	tmp.u=u,tmp.len=len,tmp.c=c;
	return tmp;
}
bool operator<(const jgt& oa,const jgt& ob)
{
	if(oa.c!=ob.c) return oa.c>ob.c;
	else return oa.len>ob.len;
}
vector<priority_queue<jgt> >q;
int len;
priority_queue<jgt>tmp,add;
void init()
{
	for(int i=1;i<=n;i++) a[i].clear();
	for(int i=1;i<=n;i++) ans[i]=-1;
	for(int i=1;i<=n;i++) v[i]=0;
	q.clear();
	while(tmp.size()) tmp.pop();
	while(add.size()) add.pop();
}
void solve()
{
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++)
	{
		int u,v;
		char w;
		cin>>u>>v>>w;
		if(a[u].size())
		{
			char cc=a[u][0].first;
			if(cc>w)
			{
				a[u].clear();
				a[u].push_back(make_pair(w,v));
			}
			else if(cc==w) a[u].push_back(make_pair(w,v));
		}
		else a[u].push_back(make_pair(w,v));
		if(a[v].size())
		{
			char cc=a[v][0].first;
			if(cc>w)
			{
				a[v].clear();
				a[v].push_back(make_pair(w,u));
			}
			else if(cc==w) a[v].push_back(make_pair(w,u));
		}
		else a[v].push_back(make_pair(w,u));
	}
	tmp.push(mj(1,0,'a'-1));
	q.push_back(tmp);
	++len;
	while(len)
	{
		tmp=q[len-1];
		while(tmp.size())
		{
			jgt tp=tmp.top();
			if(v[tp.u]) tmp.pop();
			else break;
		}
		if(tmp.empty())
		{
			q.pop_back();
			--len;
			continue;
		}
		char mi;
		mi=tmp.top().c;
		while(add.size()) add.pop();
		while(tmp.size()&&tmp.top().c==mi)
		{
			jgt tp=tmp.top();
			tmp.pop();
			int u=tp.u;
			if(v[u]) continue;
			ans[u]=tp.len;
			v[u]=1;
			int lentmp=a[u].size();
			for(int i=0;i<lentmp;i++)
			{
				int to=a[u][i].second;
				if(v[to]) continue;
				add.push(mj(to,tp.len+1,a[u][i].first));
			}
		}
		if(tmp.empty())
		{
			q.pop_back();
			--len;
		}
		q.push_back(add);
		++len;
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
	cout<<'\n';
}
int main()
{
	freopen("Path.in","r",stdin);
	freopen("Path.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}