#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

#define ciallo(x) cerr << x << ' '
#define Ciallo(x) cerr << x << '\n'
const int MAXN = 2 * 1e5 + 5;
const int INF = 1e9;
int n, m, T;

namespace task{
	struct node{
		int to, nxt, len;
	}e[MAXN << 1];
	
	int h[MAXN], tot = 0, d[MAXN], ans[MAXN];
	
	void add(int x, int y, int len){
		e[++ tot] = {y, h[x], len};
		h[x] = tot;
	}
	void clear(){
		tot = 0;
		for(int i = 1;i <= n;i ++){
			d[i] = 0;
			h[i] = 0;
			ans[i] = -1;
		}
	}
	
//	bool Dijsktra(){
//		for(int i = 1;i <= n;i ++){
//			d[i] = INF;
//		}
//		d[1] = 0;
//		for(int i = h[1];i;i = e[i].nxt){
//			q.push({e[i].len, 1});
//		}
//		while(!q.empty()){
//			qp cnt = q.top(); q.pop();
//			int u = cnt.now;
//			vis[u] ++;
//			if(vis[u] > n) return false;
//			for(int i = h[u];i;i = e[i].nxt){
//				int v = e[i].to;
//				d[v] = d[u] + 1;
//				q.push({e[i].len, v});
//			}
//		}
//		return true;
//	}
	
	void bfs(){
		vector<int> cur;
		ans[1] = 0;
		cur.push_back(1);
		while(!cur.empty()){
			int minx = 114514;
			for(int u : cur){
//				ciallo(u);
				for(int i = h[u];i;i = e[i].nxt){
					if(e[i].len < minx){
						minx = e[i].len;
					}
				}
			}
			if(minx == 114514) break;
			vector<int> nxt;
			for(int u : cur){
				for(int i = h[u];i;i = e[i].nxt){
					int v = e[i].to;
					int l = e[i].len;
					if(l == minx && ans[v] == -1){
						ans[v] = ans[u] + 1;
						nxt.push_back(v);
					}
				}
			}
			sort(nxt.begin(), nxt.end());
			nxt.erase(unique(nxt.begin(), nxt.end()), nxt.end());
//			for(int x : nxt) ciallo(x);
			cur = nxt;
		}
	}
}

void solve(){
	cin >> n >> m;
	task::clear();
	for(int i = 1;i <= m;i ++){
		int u, v; char c;
		cin >> u >> v >> c;
		task::add(u, v, (c - 'a'));
		task::add(v, u, (c - 'a'));
	}
	task::bfs();
	for(int i = 1;i <= n;i ++){
		cout << task::ans[i];
		if(i != n) cout << ' ';
	}
	cout << '\n';
}

int main(){
	freopen("Path.in", "r", stdin);
	freopen("Path.out", "w", stdout);
	cin.tie(0) -> ios::sync_with_stdio(0);
	cin >> T;
	
	while(T --){
		solve();
	}
	
	return 0;
}