#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct node{
	int to;
	char c;
};

int n,m;
int ans[410000];


void solve(){
	cin>>n>>m;
	vector <vector <node> > a(n+10);
	for (int i=1;i<=m;i++){
		int u,v;
		char c;
		cin>>u>>v>>c;
		a[u].push_back({v,c});
		a[v].push_back({u,c});
	}
	for (int i=0;i<=n+5;i++){
		ans[i]=-2;
	}
	ans[1]=0;
	vector<int> q={1};
    for (int i=1;i<=n;i++){
        if (q.empty()) break;
        char minn=127;
        for (int u:q){
            for (auto&v:a[u]){
                if (v.c<minn) minn=v.c;
            }
        }
        vector<int> nxt;
        for (int u:q){
            for (auto&v:a[u]){
                if (v.c==minn){
                    if (ans[v.to]==-2){
                        if (i==n) ans[v.to]=-1;
                        else ans[v.to]=i;
                        nxt.push_back(v.to);
                    }
                }
            }
        }
        sort(nxt.begin(),nxt.end());
        nxt.erase(unique(nxt.begin(),nxt.end()),nxt.end());
        q=nxt;
    }
    for (int i=1;i<=n;++i){
        if (ans[i]<0) cout<<-1;
        else cout<<ans[i];
        cout<<(i==n?"":" ");
    }
    cout<<"\n";
}

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