#include<bits/stdc++.h>

using namespace std;

const int N=2e5+5;
int t,n,m,ans[N];
vector<pair<int,char>> e[N];
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--){
		cin>>n>>m;
		for(int i(1);i<=m;++i){
			int u,v;
			char c;
			cin>>u>>v>>c;
			e[u].push_back({v,c});
			e[v].push_back({u,c});
		}
		for(int i(1);i<=n;++i){
			ans[i]=-1;
		}
		ans[1]=0;
		queue<pair<int,char>>q;
		q.push({1,'z'+1});
		while(!q.empty()){
			char s='z';
			queue<pair<int,char>> p;
			while(!q.empty()){
				auto [u,b]=q.front();
				q.pop();
				p.push({u,b});
				for(auto&[v,c]:e[u]){
					s=min(s,c);
				}
			}
			while(!p.empty()){
				auto [u,b]=p.front();
				p.pop();
				for(auto&[v,d]:e[u]){
					if(b==s&&ans[v]>-1&&d<=b){
						ans[v]=ans[u]+1;
						q.push({v,b});
					}
				}
			}
		}
		for(int i(1);i<=n;++i){
			cout<<ans[i]<<" ";
		}
		cout<<"\n";
	}
	return 0;
}