#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
#define fi first
#define se second
#define debug printf("ciallo\n");
const int N=2e5+10;
const int M=2e5+10;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
using namespace std;
int T, n, m;
vector<int> g[N];
vector<char> e[N];
int ans[N];
void add(int u,int v,char w){
    g[u].push_back(v);
    e[u].push_back(w);
}
void bfs(int s){
    memset(ans,-1,sizeof(ans));
    queue<pair<int,char> > q;
    ans[s]=0;
    q.push({s,'z'+1});
    while(!q.empty()){
        char cmin='z';
        queue<pair<int,char> > temp;
        while(!q.empty()){
            pair<int,char> front=q.front();
			q.pop();
            int u=front.first;
            char last=front.second;
            temp.push(front);
            for(size_t i=0;i<g[u].size();i++){
                char c=e[u][i];
                if(c<cmin) cmin=c;
            }
        }
        while(!temp.empty()){
            pair<int, char> front=temp.front();
			temp.pop();
            int u=front.first;
            char last=front.second;
            for(size_t i=0;i<g[u].size();i++){
                int v=g[u][i];
                char c=e[u][i];
                if(c==cmin&&c<=last&&ans[v]==-1){
                    ans[v]=ans[u]+1;
                    q.push(mk(v,c));
                }
            }
        }
    }
}

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();
            e[i].clear();
        }
        for(int i=1;i<=m;i++){
            int x,y;
            char c;
            cin>>x>>y>>c;
            add(x,y,c);
            if(x!=y) add(y,x,c);
        }
        bfs(1);
        for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
        cout<<endl;
    }
    return 0;
}