#include<bits/stdc++.h>
#define pr pair<int,int>
using namespace std;
const int N=2e5+2;
int n,m;
int d[N];
bool vis[N];
vector<int> g[N];
void bfs(){
	queue<int> q;
	vis[1]=1;d[1]=0;
	for(int i=0;i<g[1].size();i++){
		int u=g[1][i];
		d[u]=1;vis[u]=1;
		q.push(u);
	}
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=0;i<g[x].size();i++){
			int u=g[x][i];
			if(vis[u]) continue;
			d[u]=d[x]+1;vis[u]=1;
			q.push(u);
		}
		g[x].clear();
	}
}
int main()
{
	freopen("Path.in","r",stdin);
	freopen("Path.out","w",stdout);
	int T;cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=2;i<=n;i++) d[i]=1e9,vis[i]=0;
		while(m--){
			int u,v; char w;
			cin>>u>>v>>w;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		bfs();
		for(int i=1;i<=n;i++) cout<<d[i]<<" ";
		cout<<endl;
	}
	return 0;
}