#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int T,n,m,mk[N],dis[N];
int head[N],tot;
struct edge {
	int v,nxt;
	char w;
}e[N*2];
void add (int u,int v,char w) {
	e[++tot].v=v;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}
queue<int>q1,q2;
void bfs () {
	memset(mk,0,sizeof(mk));
	memset(dis,0,sizeof(dis));
	q1.push(1);
	while (!q1.empty()) {
		int mn='z';
		while (!q1.empty()) {
			int u=q1.front();
			q1.pop();
			q2.push(u);
			for (int i=head[u];i;i=e[i].nxt) {
				int w=e[i].w;
			    mn=min(mn,w);
			}
		}
		while (!q2.empty()) {
			int u=q2.front();
			q2.pop();
			for (int i=head[u];i;i=e[i].nxt) {
				int v=e[i].v;
				char w=e[i].w;
				if (int(w)==mn&&mk[v]==0) {
					mk[v]=1;
				    dis[v]=dis[u]+1;
				    q1.push(v);
				}
			}
		}
	}
}
int main () {
	freopen("Path.in","r",stdin);
	freopen("Path.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> T;
	while (T--) {
		memset(head,0,sizeof(head));
		tot=0;
		cin >> n >> m;
		for (int i=1;i<=m;i++) {
			int a,b;
			char c;
			cin >> a >> b >> c;
			add(a,b,c);
			add(b,a,c);
		}
		bfs();
		cout << 0 <<' ';
		for (int i=2;i<=n;i++) {
			if (dis[i]==0) cout << -1 <<' ';
			else cout << dis[i] <<' ';
		}
		cout <<endl;
	}
	return 0;
}