#include <cstdio>
#include <queue>
using namespace std;
const int N=2e5+10,M=4e5+10;
int n,m,ver[N],nxt[M*2],to[M*2],val[M*2],idx,ans[N];
struct Node{int ch,u;};
queue<Node>q,tmp;
void add(int x,int y,int z){
    to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx,val[idx]=z;
}
int main(){
	freopen("Path.in","r",stdin);
	freopen("Path.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            ver[i]=0;
            ans[i]=-1;
        }
        idx=0;
        for(int i=1;i<=m;i++){
            int u,v;char w[2];
            scanf("%d%d%s",&u,&v,w);
            int c=w[0]-'a';
            add(u,v,c);
            add(v,u,c);
        }
        ans[1]=0;
        while(!q.empty()) q.pop();
        while(!tmp.empty()) tmp.pop();
        q.push((Node){26,1});
        while(!q.empty()){
            int up=26;
            while(!q.empty()){
                Node node=q.front(); q.pop();
                tmp.push(node);
                int u=node.u;
                for(int i=ver[u];i;i=nxt[i]){
                    int w=val[i];
                    if(w<up)up=w;
                }
            }
            while(!tmp.empty()){
                Node node=tmp.front(); tmp.pop();
                int lst=node.ch;
                int u=node.u;
                for(int i=ver[u];i;i=nxt[i]){
                    int v=to[i];
                    int w=val[i];
                    if(w>up||w>lst||ans[v]!=-1) continue;
                    ans[v]=ans[u]+1;
                    q.push((Node){w,v});
                }
            }
        }
        for(int i=1;i<=n;i++){
            printf("%d",ans[i]);
            if(i<n)printf(" ");
        }
        printf("\n");
    }
    return 0;
}