哦，这题实在是太美妙了呀。

仔细思考发现性质：

1. 走的路径是单调不升的，因为若不是这样，就可以一直在小的字符转，最后再走大的字符。
2. 一条边中，只有最小字符的边是有用的，因为其他边都可以通过最小字符的边来让自己更小。
3. 若 $f(1,i) \le f(1,j)$ 且 $i<j$，则 $f(1,i)$ 一定是 $f(1,j)$ 的前缀。

观察以上性质，可以直接广搜。

但是实际上，每次拓展一些点（一个集合）的时候，集合里的边只有最小的能走，与性质 2 原理相同。

综上所述：只需要每次拓展拓展最小的且满足单调不增就可以了。

正常广搜就行。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int t,n,m,u,v;
char w;
vector <pair <int,int>> ve[N];
vector <int> ans;
void solve(){
	cin>>n>>m;
	ans.clear();
	ans.push_back(0);
	for(int i=1;i<=n;i++){
		ve[i].clear();
		ans.push_back(-1);
	}
	ans[1]=0;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		ve[u].push_back({v,w-'a'});
		if(u!=v) ve[v].push_back({u,w-'a'});
	}
	queue <pair <int,int>> q;
	q.push({1,26});
	while(!q.empty()){
		int mn=26;
		queue <pair <int,int>> temp;
		while(!q.empty()){
			pair <int,int> t=q.front();
			q.pop();
			temp.push({t.first,t.second});
			for(pair <int,int> v:ve[t.first]) mn=min(mn,v.second);
		}
		while(!temp.empty()){
			pair <int,int> t=temp.front();
			temp.pop();
			for(pair <int,int> v:ve[t.first]){
				if(v.second==mn&&v.second<=t.second&&ans[v.first]==-1){
					q.push({v.first,v.second});
					ans[v.first]=ans[t.first]+1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	cout<<"\n";
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--) solve();
	return 0;
}