#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;

int T,n,m;
vector<pair<int,char> > g[MAXN];
int d[MAXN],v[MAXN];
queue<int> q;

int main()
{
	freopen("Path.in","r",stdin);
	freopen("Path.out","w",stdout);
	cin>>T;
	while(T--) 
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++) g[i].clear();
		for(int i=1;i<=m;i++)
		{
			int u,vv; char c[2];
			cin>>u>>vv>>c;
			g[u].push_back(make_pair(vv,c[0]));
			g[vv].push_back(make_pair(u,c[0]));
		}
		for(int i=1;i<=n;i++) d[i]=-1,v[i]=0;
		d[1]=0;
		q.push(1);
		for(char ch='a';ch<='z';ch++)
		{
			int sz=q.size();
			if(!sz) continue;
			vector<int> cur;
			while(sz--)
			{
				int u=q.front(); q.pop();
				cur.push_back(u);
				for(int i=0;i<g[u].size();i++)
				{
					int vv=g[u][i].first;
					char c=g[u][i].second;
					if(c!=ch) continue;
					if(d[vv]==-1)
					{
						d[vv]=d[u]+1;
						q.push(vv);
					}
					else if(v[vv]==0) v[vv]=1;
				}
			}
			for(int i=0;i<cur.size();i++) v[cur[i]]=0;
		}
		for(int i=1;i<=n;i++) cout<<d[i]<<" ";
		cout<<endl;
	}
	return 0;
}